1. Introduction
Throughout the paper, graphs are simple, without loops and multiple edges. Let
be a simple graph of order n with vertex set
and edge set
. The adjacency matrix
of G is defined as follows:
if
is adjacent to
, and
otherwise. The eigenvalues
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
,
,
, respectively. Obviously
. 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
of G has many important applications in chemistry [1] .
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,
and
are called the tree, the unicycle graph, the bicycle graph and tricyclic graph.
, the vertex-induced subgraph
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.
denotes the graph
. Let G and H be two vertex disjoint graphs;
denotes the union graph of G and H. As shown in Figure 1, a graph consisting of two endpoints of a path
bonded to circle
,
and
is called ζ-graph (as
). 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
, the only induced subgraph ζ-graphs is called the kernel of graph G, as
.
2. Some Lemmas
Lemma 1 [18] Let
, where
are connected components of G. Then
(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
(2)
Figure 1. The graphs
.
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
.
Lemma 3 [4] Let T be a tree of order n. Then
,
.
For a tree T on at least two vertices, a vertex
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
be a graph containing a vertex u, and let
be a graph of order n that is disjoint from
. For
, the k-joining graph of
and
with respect to u is obtained from
by joining u and any k vertices of
; we denote it by
. Note that the graph
is not uniquely determined when
.
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 (
),
(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 (
),
(4)
Let G be a graph. The number of all odd cycles in G is denoted by
. The number of all cycles of length 4k + 3 in G is denoted by
; the number of all cycles of length 4k + 5 in G is denoted by
. Obviously,
.
Lemma 6 [18] Let the each component of graph G be a tree, unicyclic or bicyclic. Then
(5)
Lemma 7 Let
,
,
,
and
,
,
,
. Then
(6)
Proof. It can be obtained by Lemma 2.
3. Main Result
For graph
with fewer vertices, (
). We use Matlab to calculate their the positive and negative inertia indexes and nullity (Table 1). Abbreviate the graph
here to be written as G,
,
and
to p, n and
, respectively.
For a given tricycle graph
, the kernel of graph G is
, for each vertex
, let
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
. Then for all vertices
,
is a tree and G is obtained by identifying the vertex v of
with the vertex v on
. The tricycle graph G is called of Type I, if there exists a vertex v on
such that v is matched in
; otherwise, G is called of Type II.
Theorem 1 For a given tricycle graph
, the kernel of graph G is
.
1) If G is type I and the
is matched in
, then
(7)
And
is a tree,
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
,
.
(8)
Proof. 1) If G is of type I and
is matched in
, then there will exist a positive integer
such that . By Lemma 4,
(9)
And
is a tree,
is the union of trees, unicyclic graphs and bicyclic graphs.
2) If G is of Type II, suppose
contains vertices other than v, since v is mismatched in
, by Lemma 5,
(10)
Applying Lemma 5 and Lemma 1 repeatedly, we have
(11)
So the conclusion is proved.
Theorem 2 For a given triccyle graph
, then
(12)
Proof. Let the kernel of tricycle graph be
.
1) If the graph G is Type I, and the vertex v on
such that v matched in
, then
(13)
And
is a tree,
is the union of trees, unicyclic graphs and bicyclic graphs . By Lemma 6, it's true for
and
, so it's true for tricycle graph G.
2) If graph G is Type II, by Theorem 1,
(14)
Because of
is a forest. So according to the Lemma 3,
, so
, hence the conclusion is confirmed by Lemma 7 and Table 1.
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).