The Inertia Indexes of One Special Kind of Tricyclic Graphs

Show more

1. Introduction

Throughout the paper, graphs are simple, without loops and multiple edges. Let $G=\left(V,E\right)$ be a simple graph of order n with vertex set $V=\left\{{v}_{1},{v}_{2},\cdots ,{v}_{n}\right\}$ and edge set $E=E\left(G\right)$ . The adjacency matrix $A={\left({a}_{ij}\right)}_{n\times n}$ of G is defined as follows: ${a}_{ij}=1$ if ${v}_{i}$ is adjacent to ${v}_{j}$ , and ${a}_{ij}=0$ otherwise. The eigenvalues ${\lambda}_{1}\mathrm{,}{\lambda}_{2}\mathrm{,}\cdots \mathrm{,}{\lambda}_{n}$ of A are said to be the eigenvalues of the graph G, and to form the spectrum of this graph. The numbers of positive, negative and zero eigenvalues in the spectrum of the graph G are called positive and negative inertia indexes and nullity of the graph G, and are denoted by $p\left(G\right)$ , $n\left(G\right)$ , $\eta \left(G\right)$ , respectively. Obviously $p\left(G\right)+n\left(G\right)+\eta \left(G\right)=n$ . The positive and negative inertia indexes and nullity of the graph G are collectively called inertia indexes of the graph G.

Let G be a graph, then the nullity $\eta \left(G\right)$ of G has many important applications in chemistry [1] . $\eta \left(G\right)=0$ is a necessary condition for the chemical stability of the molecules shown in the graph G [1] . 1957, Collatz and Sinogowitz in [2] put forward a question that how to find out all singular graphs, namely, to describe all graphs with nullity that are greater than zero. It was a very difficult problem only with some special results [3] [4] [5] [6] [7] . In mathematics, the inertia indexes of the graphs are related to the complete decomposition of multiple graphs. Many graph theory scholars have carried a lot of researches on this topic, and made great progress. At the same time, many conclusions had been obtained. In [3] - [19] , the inertia indexes is researched as several kinds of graphs such as trees, unicyclic graphs, bicyclic graphs and tricyclic graphs. In [18] , a calculation method is given about the inertia indexes of trees, unicyclic graphs, bicyclic graphs, and a conjecture is put forward about the signature of graphs. In [19] , the tricyclic graphs are divided into 15 categories. In [20] [21] , the inertia indexes are studied by four special kinds of tricyclic graphs. In this paper, the inertia indexes of a special kinds of tricyclic graphs different from literatures [20] [21] are studied, and a new calculation method is given by deleting pendant trees and compressing internal paths and Matlab software.

Let G be a connected graph of order n, the graphs respectively with size $n-1$ , n, $n+1$ and $n+2$ are called the tree, the unicycle graph, the bicycle graph and tricyclic graph. $U\subseteq V\left(G\right)$ , the vertex-induced subgraph $G\left[U\right]$ is the subgraph of G whose vertex set is U and whose edge set consists of all edges of G which have both ends in U. $G\backslash U$ denotes the graph $G\left[V\left(G\right)\backslash U\right]$ . Let G and H be two vertex disjoint graphs; $G\cup H$ denotes the union graph of G and H. As shown in Figure 1, a graph consisting of two endpoints of a path ${P}_{p}$ bonded to circle ${C}_{m}$ , ${C}_{n}$ and ${C}_{q}$ is called ζ-graph (as $\zeta \left(m\mathrm{,}n\mathrm{,}p\mathrm{,}q\right)$ ). As known to all, the tricyclic graphs can be divided into 15 categories: γ = {all tricyclic graphs that contain an induced subgraph ζ-graphs} is one category of the 15 categories. For a given tricycle graph $G\in \gamma $ , the only induced subgraph ζ-graphs is called the kernel of graph G, as $\chi \left(G\right)$ .

2. Some Lemmas

Lemma 1 [18] Let $G={G}_{1}\cup {G}_{2}\cup \cdots \cup {G}_{t}$ , where ${G}_{i}\left(i=1,2,\cdots ,t\right)$ are connected components of G. Then

$p\left(G\right)={\displaystyle \underset{i=1}{\overset{t}{\sum}}}\text{\hspace{0.05em}}p\left({G}_{i}\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}n\left(G\right)={\displaystyle \underset{i=1}{\overset{t}{\sum}}}\text{\hspace{0.05em}}n\left({G}_{i}\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}\eta \left(G\right)={\displaystyle \underset{i=1}{\overset{t}{\sum}}}\text{\hspace{0.05em}}\eta \left({G}_{i}\right).$ (1)

Lemma 2 [18] Let G be a graph containing path with four vertices of degree 2 as shown in Figure 2. Let the graph H be obtained form G by replacing this path with an edge. Then

$p\left(G\right)=p\left(H\right)+2,\text{\hspace{0.17em}}\text{\hspace{0.17em}}n\left(G\right)=n\left(H\right)+2,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\eta \left(G\right)=\eta \left(H\right).$ (2)

Figure 1. The graphs $\zeta \left(m\mathrm{,}n\mathrm{,}p\mathrm{,}q\right)$ .

Figure 2. The graphs G and H is described in the Lemma 2.

A matching of G is a collection of independent edges of G. A maximal matching is a matching with the maximum possible number of edges. A matching M of G is called perfect if every vertex of G is incident with (exactly) one edge in M. Obviously, a perfect matching is a maximum matching. The size of a maximal matching of G, i.e., the maximum number of independent edges in G, is called the matching number of G, denoted by $\mu \left(G\right)$ .

Lemma 3 [4] Let T be a tree of order n. Then $p\left(T\right)=n\left(T\right)=\mu \left(T\right)$ , $\eta \left(T\right)=n-2\mu \left(T\right)$ .

For a tree T on at least two vertices, a vertex $v\in T$ is called mismatched in T if there exists a maximum matching M of T that does not cover v; otherwise, v is called matched in T. If a tree consists of only one vertex, then this vertex is considered as mismatched. Let ${G}_{1}$ be a graph containing a vertex u, and let ${G}_{2}$ be a graph of order n that is disjoint from ${G}_{1}$ . For $1\le k\le n$ , the k-joining graph of ${G}_{1}$ and ${G}_{2}$ with respect to u is obtained from ${G}_{1}\cup {G}_{2}$ by joining u and any k vertices of ${G}_{2}$ ; we denote it by ${G}_{1}\left(u\right){\odot}^{k}{G}_{2}$ . Note that the graph ${G}_{1}\left(u\right){\odot}^{k}{G}_{2}$ is not uniquely determined when $n>k$ .

Lemma 4 [18] Let T be a tree with a matched vertex u and let G be a graph of order n. Then for each positive integer k ( $1\le k\le n$ ),

$\begin{array}{l}p\left(T\left(u\right){\odot}^{k}G\right)=p\left(T\right)+p\left(G\right)\mathrm{,}\\ n\left(T\left(u\right){\odot}^{k}G\right)=n\left(T\right)+n\left(G\right)\mathrm{,}\\ \eta \left(T\left(u\right){\odot}^{k}G\right)=\eta \left(T\right)+\eta \left(G\right)\mathrm{.}\end{array}$ (3)

Lemma 5 [18] Let T be a tree with a mismatched vertex u and let G be a graph of order n. Then for each positive integer k ( $1\le k\le n$ ),

$\begin{array}{l}p\left(T\left(u\right){\odot}^{k}G\right)=p\left(T-u\right)+p\left(G+u\right)=p\left(T\right)+p\left(G+u\right)\mathrm{,}\\ n\left(T\left(u\right){\odot}^{k}G\right)=n\left(T-u\right)+n\left(G+u\right)=n\left(T\right)+n\left(G+u\right)\mathrm{,}\\ \eta \left(T\left(u\right){\odot}^{k}G\right)=\eta \left(T-u\right)+\eta \left(G+u\right)=\eta \left(T\right)+\eta \left(G+u\right)\mathrm{.}\end{array}$ (4)

Let G be a graph. The number of all odd cycles in G is denoted by ${c}_{1}\left(G\right)$ . The number of all cycles of length 4k + 3 in G is denoted by ${c}_{3}\left(G\right)$ ; the number of all cycles of length 4k + 5 in G is denoted by ${c}_{5}\left(G\right)$ . Obviously, ${c}_{3}\left(G\right)+{c}_{5}\left(G\right)={c}_{1}\left(G\right)$ .

Lemma 6 [18] Let the each component of graph G be a tree, unicyclic or bicyclic. Then

$-{c}_{3}\left(G\right)\le p\left(G\right)-n\left(G\right)\le {c}_{5}\left(G\right)\mathrm{.}$ (5)

Lemma 7 Let $m\ge 3$ , $n\ge 3$ , $p\ge 2$ , $q\ge 3$ and $m=4k+{m}^{\prime}\left(3\le {m}^{\prime}\le 6\right)$ , $n=4s+{n}^{\prime}\left(3\le {n}^{\prime}\le 6\right)$ , $p=4t+{p}^{\prime}\left(2\le {p}^{\prime}\le 5\right)$ , $q=4y+{q}^{\prime}\left(3\le {q}^{\prime}\le 6\right)$ . Then

$\begin{array}{l}p\left(\zeta \left(m,n,p,q\right)\right)=2\left(k+s+t+y\right)+p\left(\zeta \left({m}^{\prime},{n}^{\prime},{p}^{\prime},{q}^{\prime}\right)\right),\\ n\left(\zeta \left(m,n,p,q\right)\right)=2\left(k+s+t+y\right)+n\left(\zeta \left({m}^{\prime},{n}^{\prime},{p}^{\prime},{q}^{\prime}\right)\right),\\ \eta \left(\zeta \left(m,n,p,q\right)\right)=2\left(k+s+t+y\right)+\eta \left(\zeta \left({m}^{\prime},{n}^{\prime},{p}^{\prime},{q}^{\prime}\right)\right).\end{array}$ (6)

Proof. It can be obtained by Lemma 2. $\square $

3. Main Result

For graph $\zeta \left(m\mathrm{,}n\mathrm{,}p\mathrm{,}q\right)$ with fewer vertices, ( $3\le m,n,q\le 6,2\le p\le 5,m\le n$ ). We use Matlab to calculate their the positive and negative inertia indexes and nullity (Table 1). Abbreviate the graph $\zeta \left(m\mathrm{,}n\mathrm{,}p\mathrm{,}q\right)$ here to be written as G, $p\left(G\right)$ , $n\left(G\right)$ and $\eta \left(G\right)$ to p, n and $\eta $ , respectively.

For a given tricycle graph $G\in \gamma $ , the kernel of graph G is $\chi \left(G\right)$ , for each vertex $v\in V\left(\chi \left(G\right)\right)$ , let $G\left\{v\right\}$ be the induced connected subgraph of G with the maximum possible number of vertices, which contains the vertex v and contains no other vertices of $\chi \left(G\right)$ . Then for all vertices $v\in V\left(\chi \left(G\right)\right)$ , $G\left\{v\right\}$ is a tree and G is obtained by identifying the vertex v of $G\left\{v\right\}$ with the vertex v on $\chi \left(G\right)$ . The tricycle graph G is called of Type I, if there exists a vertex v on $\chi \left(G\right)$ such that v is matched in $G\left\{v\right\}$ ; otherwise, G is called of Type II.

Theorem 1 For a given tricycle graph $G\in \gamma $ , the kernel of graph G is $\chi \left(G\right)$ .

1) If G is type I and the $v\in V\left(\chi \left(G\right)\right)$ is matched in $G\left\{v\right\}$ , then

$\begin{array}{l}p\left(G\right)=p\left(G\left\{v\right\}\right)+p\left(G-G\left\{v\right\}\right),\\ n\left(G\right)=n\left(G\left\{v\right\}\right)+n\left(G-G\left\{v\right\}\right),\\ \eta \left(G\right)=\eta \left(G\left\{v\right\}\right)+\eta \left(G-G\left\{v\right\}\right).\end{array}$ (7)

And $G\left\{v\right\}$ is a tree, $G-G\left\{v\right\}$ is the union of trees, unicyclic graphs and bicyclic graphs.

2) If G is of type II, then

Table 1. Positive and negative inertia indexes and nullity of tricyclic graph $\zeta \left(m\mathrm{,}n\mathrm{,}p\mathrm{,}q\right)$ , $\left(3\le m\mathrm{,}n\mathrm{,}q\le \mathrm{6,2}\le p\le \mathrm{5,}m\le n\right)$ .

$\begin{array}{l}p\left(G\right)=p\left(G-\chi \left(G\right)\right)+p\left(\chi \left(G\right)\right),\\ n\left(G\right)=n\left(G-\chi \left(G\right)\right)+n\left(\chi \left(G\right)\right),\\ \eta \left(G\right)=\eta \left(G-\chi \left(G\right)\right)+\eta \left(\chi \left(G\right)\right).\end{array}$ (8)

Proof. 1) If G is of type I and $v\in V\left(\chi \left(G\right)\right)$ is matched in $G\left\{v\right\}$ , then there will exist a positive integer $k\in \left\{\mathrm{2,3,5}\right\}$ such that . By Lemma 4,

$\begin{array}{l}p\left(G\right)=p\left(G\left\{v\right\}\right)+p\left(G-G\left\{v\right\}\right),\\ n\left(G\right)=n\left(G\left\{v\right\}\right)+n\left(G-G\left\{v\right\}\right),\\ \eta \left(G\right)=\eta \left(G\left\{v\right\}\right)+\eta \left(G-G\left\{v\right\}\right).\end{array}$ (9)

And $G\left\{v\right\}$ is a tree, $G-G\left\{v\right\}$ is the union of trees, unicyclic graphs and bicyclic graphs.

2) If G is of Type II, suppose $G\left\{v\right\}$ contains vertices other than v, since v is mismatched in $G\left\{v\right\}$ , by Lemma 5,

$\begin{array}{l}p\left(G\right)=p\left(G\left\{v\right\}\right)+p\left(G-G\left\{v\right\}+v\right),\\ n\left(G\right)=n\left(G\left\{v\right\}\right)+n\left(G-G\left\{v\right\}+v\right),\\ \eta \left(G\right)=\eta \left(G\left\{v\right\}\right)+\eta \left(G-G\left\{v\right\}+v\right).\end{array}$ (10)

Applying Lemma 5 and Lemma 1 repeatedly, we have

$\begin{array}{l}p\left(G\right)={\displaystyle \underset{v\in \chi \left(G\right)}{\sum}}\left[p\left(G\left\{v\right\}\right)+p\left(G-G\left\{v\right\}+v\right)\right]=p\left(G-\chi \left(G\right)\right)+p\left(\chi \left(G\right)\right),\\ n\left(G\right)={\displaystyle \underset{v\in \chi \left(G\right)}{\sum}}\left[n\left(G\left\{v\right\}\right)+n\left(G-G\left\{v\right\}+v\right)\right]=n\left(G-\chi \left(G\right)\right)+n\left(\chi \left(G\right)\right),\\ \eta \left(G\right)={\displaystyle \underset{v\in \chi \left(G\right)}{\sum}}\left[\eta \left(G\left\{v\right\}\right)+\eta \left(G-G\left\{v\right\}+v\right)\right]=\eta \left(G-\chi \left(G\right)\right)+\eta \left(\chi \left(G\right)\right).\end{array}$ (11)

So the conclusion is proved. $\square $

Theorem 2 For a given triccyle graph $G\in \gamma $ , then

$-{c}_{3}\left(G\right)\le p\left(G\right)-n\left(G\right)\le {c}_{5}\left(G\right)\mathrm{.}$ (12)

Proof. Let the kernel of tricycle graph be $\chi \left(G\right)$ .

1) If the graph G is Type I, and the vertex v on $\chi \left(G\right)$ such that v matched in $G\left\{v\right\}$ , then

$\begin{array}{l}p\left(G\right)=p\left(G\left\{v\right\}\right)+p\left(G-G\left\{v\right\}\right),\\ n\left(G\right)=n\left(G\left\{v\right\}\right)+n\left(G-G\left\{v\right\}\right).\end{array}$ (13)

And $G\left\{v\right\}$ is a tree, $G-G\left\{v\right\}$ is the union of trees, unicyclic graphs and bicyclic graphs . By Lemma 6, it's true for $G\left\{v\right\}$ and $G-G\left\{v\right\}$ , so it's true for tricycle graph G.

2) If graph G is Type II, by Theorem 1,

$\begin{array}{l}p\left(G\right)=p\left(G-\chi \left(G\right)\right)+p\left(\chi \left(G\right)\right),\\ n\left(G\right)=n\left(G-\chi \left(G\right)\right)+n\left(\chi \left(G\right)\right).\end{array}$ (14)

Because of $G-\chi \left(G\right)$ is a forest. So according to the Lemma 3, $p\left(G-\chi \left(G\right)\right)=n\left(G-\chi \left(G\right)\right)$ , so $p\left(G\right)-n\left(G\right)=p\left(\chi \left(G\right)\right)-n\left(\chi \left(G\right)\right)$ , hence the conclusion is confirmed by Lemma 7 and Table 1. $\square $

4. Conclusion

A new calculation method of the inertia indexes of one special kind of tricyclic graphs with large vertices is given, and the inertia indexes of this tricyclic graphs with fewer vertices can be calculated by Matlab.

Funding

This work is supported by National Natural Science Foundation of China (1561056, 11661066), National Natural Science Foundation of Qinghai Provence (2016-ZJ-914), and Scientific Research Fund of Qinghai University for Nationalities (2015G02).

References

[1] Longuet-Higgins, H.C. (1950) Resonance Structures and Molecular Orbitals in Unsaturated Hydrocarbons. Journal of Chemical Physics, 18, 265-274.

https://doi.org/10.1063/1.1747618

[2] Collatz, L. and Sinogowitz, U. (1957) Spektren endlicher Grafen. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 21, 63-77.

https://doi.org/10.1007/BF02941924

[3] Sciriha, I. and Fowler, P.W. (2008) On Nut and Core Singular Fullerenes. Discrete Mathematics, 308, 267-276.

https://doi.org/10.1016/j.disc.2006.11.040

[4] Cvetković, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs-Theory and Application. Academic Press, New York.

[5] Brown, M., Kennedy, J.W. and Servatius, B. (1993) Graph Singularity. Graph Theory Notes of New York, 25, 23-32.

[6] Sciriha, I. (1998) On Singular Line Graphs of Trees. Congressus Numeratium, 135, 73-91.

[7] Sciriha, I. (2007) A Characterization of Singular Graphs. Electronic Journal of Linear Algebra, 16, 451-462.

https://doi.org/10.13001/1081-3810.1215

[8] Cheng, B. and Liu, B.L. (2011) On the Nullity of Tricyclic Graphs. Linear Algebra and Its Applications, 434, 1799-1810.

https://doi.org/10.1016/j.laa.2011.01.006

[9] Cheng, B. and Liu, B.L. (2007) On the Nullity of Graphs. Linear Algebra and Its Applications, 16, 60-67.

[10] Fan, Y.Z. and Qian, K.S. (2009) On the Nullity of Bipartite Graphs. Linear Algebra and Its Application, 430, 2943-2949.

https://doi.org/10.1016/j.laa.2009.01.007

[11] Guo, J.M., Yan, W. and Yeh, Y.N. (2009) On the Nullity and Matching Number of Unicyclic Graphs. Linear Algebra and Its Application, 431, 1293-1301.

https://doi.org/10.1016/j.laa.2009.04.026

[12] Sciriha, I. and Gutman, I. (2001) On the Nullity of Line Graphs of Trees. Discrete Mathematics, 232, 35-45.

https://doi.org/10.1016/S0012-365X(00)00187-4

[13] Tan, X.Z. and Liu, B.L. (2005) On the Nullity of Unicyclic Graphs. Linear Algebra and Its Applications, 408, 212-220.

https://doi.org/10.1016/j.laa.2005.06.012

[14] Li, W. and Chang, A. (2007) Describing the Nonsingular Unicyclic Graphs. Journal of Mathematical Study, 40, 442-445.

[15] Sciriha, I. (1998) On the Construction of Graphs of Nullity One. Discrete Mathematics, 181, 193-211.

https://doi.org/10.1016/S0012-365X(97)00036-8

[16] Hu, S., Tan, X. and Liu, B. (2008) On the Nullity of Bicyclic Graphs. Linear Algebra and Its Applications, 429, 1387-1391.

https://doi.org/10.1016/j.laa.2007.12.007

[17] Yu, G., Feng, L. and Wang, Q. (2013) Bicyclic Graphs with Small Positive Index of Inertia. Linear Algebra and Its Applications, 438, 2036-2045.

https://doi.org/10.1016/j.laa.2012.09.031

[18] Ma, H., Yang, W. and Li, S. (2013) Positive and Negative Inertia Index of a Graph. Linear Algebra and Its Applications, 438, 331-341.

https://doi.org/10.1016/j.laa.2012.07.014

[19] Li, S. and Yang, H. (2011) On Tricyclic Graphs Whose Second Largest Eigenvalue Does Not Exceed 1. Linear Algebra and Its Applications, 434, 2211-2221.

https://doi.org/10.1016/j.laa.2010.12.023

[20] Meng, X., Ma, H. and Li, S. (2013) Positive and Negative Inertia Indexes and Nullity of Two Kinds of Tricyclic Graphs. Journal of Shanxi Normal University: Natural Science Edition, 4, 16-19.

[21] Yang, C. and Ma, H. (2015) Positive and Negative Inertia Indexes and Nullity of Two Special Kinds of Tricyclic Graphs. Journal of Shandong University: Natral Science Edition, 4, 32-37.