The singularity of two kinds of tricyclic graphs

Abstract

Let $ G $ be a finite simple graph and let $ A(G) $ be its adjacency matrix. Then $ G $ is $ singular $ if $ A(G) $ is singular. Suppose $ P_{b_{1}}, P_{b_{2}}, P_{b_{3}} $ are three paths with disjoint vertices, where $ b_i\geq 2 (i = 1, 2, 3) $, and at most one of them is 2. Coalescing together one of the two end vertices of each of the three paths, and coalescing together the other end vertex of each of the three paths, the resulting graph is called the $ \theta $-graph, denoted by $ \theta(b_{1}, b_{2}, b_{3}) $. Let $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ be the graph obtained by merging one end of the path $ P_{s} $ with one vertex of a cycle $ C_{a} $, and merging the other end of the path $ P_{s} $ with one vertex of $ \theta(b_{1}, b_{2}, b_{3}) $ of degree 3. If $ s = 1 $, denote $ \beta(a, b_{1}, b_{2}, b_{3}) = \alpha(a, b_{1}, b_{2}, b_{3}, 1) $. In this paper, we give the necessity and sufficiency condition for the singularity of $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ and $ \beta(a, b_{1}, b_{2}, b_{3}) $, and we also prove that the probability that any given $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ is a singular graph is equal to $ \frac{35}{64} $, the probability that any given $ \beta(a, b_{1}, b_{2}, b_{3}) $ is a singular graph is equal to $ \frac{9}{16} $. From our main results we can conclude that such a $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ graph ($ \beta(a, b_{1}, b_{2}, b_{3}) $ graph) is singular if $ 4|a $ or three $ b_i (i = 1, 2, 3) $ are all odd numbers or exactly two of the three $ b_i (i = 1, 2, 3) $ are odd numbers and the length of the cycle formed by the two odd paths in $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ graph ($ \beta(a, b_{1}, b_{2}, b_{3}) $ graph) is a multiple of 4. The theoretical probability of these graphs being singular is more than half.

Keywords

• adjacency matrix
• singular graphs
• probability
• nullity