1. Introduction
This paper only considers finite and undirected simple graphs. Let G is a graph with n points, its adjacency matrix can be represented by the following matrix:
where
represents the point i and point j are adjacent. The eigenvalues of any graph G are the eigenvalues of its adjacency matrix
, and these n eigenvalues is called the spectrum of graph G. The number of non-zero eigenvalues in the spectrum of G are called the rank of G, denoted by
. The number of zero eigenvalues in the spectrum of G are called the the nullity of G, denoted by
. Obviously,
. G is singular if and only if the adjacency matrix of graph G is singular. And
is singular if and only if there is at least one zero eigenvalue.
In chemistry, we can use graphs to represent molecular diagrams of molecules, and the application of the nullity (or rank) of graphs is very extensive (see [1] - [6] ). In [6] , it proposes that the nullity of a molecular graphs is a necessary condition for the stability of the molecular chemical properties. In addition, how to characterize all graphs with nullity greater than zero is also a problem that we have been exploring, it was proposed in 1957 (see [2] ). Many scholars have attempted to characterize this type of graph which also known as singular graphs, but this problem is very difficult and still unresolved. So far, there are only some results for special graphs (see [7] - [16] ). In order to better characterize this type of graph, some mathematical scholars attempt to explore the mutual influence between the nullity of the graph and the structure of the graph by studying the structural characteristics of singular graphs (see [17] [18] [19] [20] [21] ). Some works by researchers have shown significant connections between singular graphs and other fields of mathematics (see [22] [23] [24] [25] ). Recently, we give the necessity and sufficiency of the singular of some classes tricycle graphs and probability of the occurence of these singular graphs [26] [27] .
The subgraph of graph G where each branch is an isolated edge or cycle is called the basic Sachs subgraph of graph G. The basic subgraph containing all points of G is called a basic spanning subgraph or a spanning Sachs subgraph. A basic spanning subgraph only composed of isolated edges is called a perfect matching of graph G. Of course, if a graph has a perfect matching, the number of points on the graph must be even. Let Pn, Cn and Kn denote the path, cycle and complete graph with n vertices, respectively. Let
be the union of two graphs G and H. For the notations and terms which are not defined above, please refer to [1] .
There are 4 paths, the starting points of the four paths are bonded into one point, and the ending point of each path is bonded to a cycle respectively, so this graph is called a kind of quadcyclic peacock graph. And in this kind of quadcyclic peacock graph assuming the number of points on the four cycles is
, and the number of points on the four paths is
. This type of graph is denoted by
, called γ graph (see Figure 1). And let
, this type four cycles peacock graph called δ graph (see Figure 2). In this paper, we give the necessary and sufficient conditions for the singularity of γ graph and δ graph. This paper is a generalization of [26] [27] , and has a certain promotion effect on the better characterization of singular graphs, and is also an application of nullity in graph theory.
In this paper,
collectively referred to as four a.
collectively referred to as four s. A path with the odd number of points is called a odd path, and a path with the even same as above is called even path.
The main conclusions are the following theorem and corollary.
Theorem 1.
is singular if and only if one of the following holds:
(i) At least the length of one cycle is a multiple of 4.
(ii) If there are four even cycles, at most two s are even or four s are even.
(iii) If there are three even cycles, at least two s which connected to even cycles are odd.
(iv) If there are two even cycles, (1) s which connected to even cycles are odd, (2) s which connected to even cycles are even and the s which connected to odd cycles have same parity and the length of the two odd cycles is different with respect module 4.
(v) If there is no even cycle, (1) the parity of the four s is same and four a is exactly two module 4 remainder 1 and two module 4 remainder 3, (2) exactly two s are odd and two s are even and the a which connected to the s with the same parity is different with respect module 4.
By theorem 1, the following corollary 1 is obvious.
Corollary 1.
is singular if and only if one of the following holds:
(i) At least the length of one cycle is a multiple of 4.
(ii) There are four even cycles or three even cycles or two even cycles.
2. Some Lemmas
Lemma 2. [1] Suppose
, where
are connected components of G. Then
. Equivalently, G is non-singular if and only if each
is non-singular.
Lemma 3. [1] If G is a graph with n vertices and adjacency matrix is
, then
is the set of spanning Sachs subgraph of G,
is the number of the components in H,
is the number of cycles in H.
3. Proof of the Theorem
Proof.
. Combine the parity of the a1, a2, a3, a4, s1, s2, s3, s4 and the symmetry of graph γ, we will discuss as follows.
1 Four a are even.
1.1 Four s are even. G has no spanning Sachs subgraph, G is singular.
1.2 Three s are even. We can assume that s1, s2, s3 are even, s4 is odd.
The spanning Sachs subgraphs of graph G with four cycles have:
(one).
The spanning Sachs subgraphs of graph G with three cycles have:
(two),
(two),
(two),
(two).
The spanning Sachs subgraphs of graph G with two cycles have:
(four),
(four),
(four),
(four),
(four),
(four).
The spanning Sachs subgraphs of graph G with one cycle have:
(eight),
(eight),
(eight),
(eight).
It contains 16 perfect matchings.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
if and only if
if and only if
,
,
or
, if and only if the length of any cycle is a multiple of 4.
1.3 Two s or one s or no s is even. In these cases, G has no spanning Sachs subgraph, G is singular.
2 Three a are even. We can assume that a1, a2, a3 are even, a4 is odd.
2.1 Four s or three s are even. Similar to case 1.2, in these cases we can get that G is singular if and only if the length of any cycle is a multiple of 4.
2.2 Two s are even.
2.2.1 If s4 is contained in two s. Let’s assume that s3, s4 are even, s1, s2 are odd. G has no spanning Sachs subgraph, G is singular.
2.2.2 If s4 is not contained in two s. Let’s assume that s1, s2 are even, s3, s4 are odd. Similar to case 1.2, we can get that G is singular if and only if the length of any cycle is a multiple of 4.
2.3 One s or no s is even. In these cases, G has no spanning Sachs subgraph, G is singular.
3 Two a are even. We can assume that a1, a2 are even, a3, a4 are odd.
3.1 Four s are even. There is no the spanning Sachs subgraph with four cycles. The spanning Sachs subgraphs of graph G with three cycles have:
(one),
(one).
The spanning Sachs subgraphs of graph G with two cycles have:
(two),
(two),
(two),
(two).
The spanning Sachs subgraphs of graph G with one cycle have:
(four),
(four).
There is no perfect matching.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
if and only if
if and only if
,
or
, if and only if the length of any cycle is a multiple of 4 or the length of the two odd cycles is module 4 with different remainder.
3.2 Three s are even.
3.2.1 If s1 and s2 are all contained in three s. Let’s assume that s1, s2, s3 are even, s4 is odd. The spanning Sachs subgraphs of graph G with four cycles have:
(one).
The spanning Sachs subgraphs of graph G with three cycles have:
(two),
(two).
The spanning Sachs subgraphs of graph G with two cycles have:
(four),
(one).
The spanning Sachs subgraphs of graph G with one cycle have:
(two),
(two).
It contains 4 perfect matchings.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
if and only if
obviously, the first equation is equal to 0 without a solution, if and only if
or
, if and only if the length of any cycle is a multiple of 4.
3.2.2 If s1 and s2 are not all contained in three s. Let’s assume that s1, s3, s4 are even, s2 is odd. Similar to case 1.2, we can get that G is singular if and only if the length of any cycle is a multiple of 4.
3.3 Two s are even.
3.3.1 If s1, s2 are contained in two s exactly. Let’s assume that s1, s2 are even, s3, s4 are odd. Similar to subcase 3.1, it is obtained that G is singular if and only if the length of any cycle is a multiple of 4 or the length of the two odd cycles is module 4 with different remainder.
3.3.2 If one of s1, s2 is contained in two s. Let’s assume that s1, s3 are even, s2, s4 are odd. Similar to case 1.2, we can get that G is singular if and only if the length of any cycle is a multiple of 4.
3.3.3 If s1, s2 are not contained in two s exactly. Let’s assume that s3, s4 are even, s1, s2 are odd. G has no spanning Sachs subgraph, G is singular.
3.4 One s is even.
3.4.1 If s1 or s2 is contained in one s. Let’s assume that s1 is even, s2, s3, s4 are odd. Similar to case 1.2, we can get that G is singular if and only if the length of any cycle is a multiple of 4.
3.4.2 If s1 or s2 is not contained in one s. Let’s assume that s3 is even, s1, s2, s4 are odd. G has no spanning Sachs subgraph, G is singular.
3.5 Four s are odd. G has no spanning Sachs subgraph, G is singular.
4 One a is even. We can assume that a1 is even, a2, a3, a4 are odd.
4.1 Four s are even. There is no the spanning Sachs subgraph with four cycles. The spanning Sachs subgraphs of graph G with three cycles have:
(one),
(one),
(one).
The spanning Sachs subgraphs of graph G with two cycles have:
(two),
(two),
(two).
There is no the spanning Sachs subgraph with one cycle. There is no perfect matching.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
if and only if
due to
, the above equation holds if and only if
, if and only if the length of any cycle is a multiple of 4.
4.2 Three s are even.
4.2.1 If s1 is contained in three s. Let’s assume that s1, s2, s3 are even, s4 is odd. The spanning Sachs subgraphs of graph G with four cycles have:
(one).
The spanning Sachs subgraphs of graph G with three cycles have:
(two).
The spanning Sachs subgraphs of graph G with two cycles have:
(one),
(one).
The spanning Sachs subgraphs of graph G with one cycle have:
(two),
(two).
There is no perfect matching.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
if and only if
if and only if
, if and only if the length of any cycle is a multiple of 4.
4.2.2 If s1 is not contained in three s. Let’s assume that s2, s3, s4 are even, s1 is odd. Similar to case 1.2, we can get that G is singular if and only if the length of any cycle is a multiple of 4.
4.3 Two s are even.
4.3.1 If s1 is contained in two s. Let’s assume that s1, s2 are even, s3, s4 are odd. There is no the spanning Sachs subgraph with four cycles. The spanning Sachs subgraphs of graph G with three cycles have:
(one),
(one).
The spanning Sachs subgraphs of graph G with two cycles have:
(two),
(two).
The spanning Sachs subgraphs of graph G with one cycle have:
(one).
It contains 2 perfect matchings.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
if and only if
if and only if
, if and only if the length of any cycle is a multiple of 4.
4.3.2 If s1 is not contained in two s. Let’s assume that s3, s4 are even, s1, s2 are odd. Similar to case 1.2, we can get that G is singular if and only if the length of any cycle is a multiple of 4.
4.4 One s or no s is even. Similar to case 4.1, in these cases we can get that G is singular if and only if the length of any cycle is a multiple of 4.
5 Four a are odd.
5.1 Four s are even. There is no the spanning Sachs subgraph with four cycles. The spanning Sachs subgraphs of graph G with three cycles have:
(one),
(one),
(one),
(one).
There is no the spanning Sachs subgraph with one or two cycles. There is no perfect matching.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
if and only if four a is exactly two module 4 remainder 1 and two module 4 remainder 3.
5.2 Three s are even. We can assume that s1, s2, s3 are even, s4 is odd. The spanning Sachs subgraphs of graph G with four cycles have:
(one).
There is no the spanning Sachs subgraph with three cycles. The spanning Sachs subgraphs of graph G with two cycles have:
(one),
(one),
(one).
There is no the spanning Sachs subgraph with one cycle. There is no perfect matching.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
it is impossible to establish.
5.3 Two s are even. We can assume that s1, s2 are even, s3, s4 are odd. There is no the spanning Sachs subgraph with four cycles. The spanning Sachs subgraphs of graph G with three cycles have:
(one),
(one).
There is no the spanning Sachs subgraph with two cycles. The spanning Sachs subgraphs of graph G with one cycle have:
(one),
(one).
There is no perfect matching.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
if and only if
is module 4 with different remainder and
is module 4 with different remainder.
5.4 One s is even. We can assume that s1 is even, s2, s3, s4 are odd. There is no the spanning Sachs subgraph with four or three cycles. The spanning Sachs subgraphs of graph G with two cycles have:
(one),
(one),
(one).
There is no the spanning Sachs subgraph with one cycle. It contains 1 perfect matching.
By Lemma 2.2, G is singular if and only if
multiply both sides by
, if and only if
it is impossible to establish.
5.5 Four s is odd. Similar to case 5.1, we can get G is singular if and only if four a is exactly two module 4 remainder 1 and two module 4 remainder 3.
The Theorem 1.1 is proved by summarizing the above cases.
Acknowledgements
Supported by National Natural Science Foundation of China (11561056), National Natural Science Foundation of Qinghai Provence (2022-ZJ-924), and Innovation Project of Qinghai Minzu University (07M2022002).