Substituted Graph Based On Graph Operation And Its Spanning Tree Count

Substituted graph is a kind of network graph with complex structure.This concept originates from the definition of Bela Bollobas.Because the substituted graph is constructed by copying the original network and adding edges between their replicates,it can greatly improve the complexity of the original network.Genetic networks in complex networks are also constructed based on this.The number of spanning trees of a graph is an important invariant of a graph and an important quantitative indicator of network reliability,and has a wide application background.For example,the design of optimized circuits in circuit analysis,the calculation of isomers with specific structures in quantum chemistry,and the optimization planning of distribution network frame.In general,it is not easy to accurately calculate the number of spanning trees of a graph.It is NP-hard.In 1847,Kirchhoff proved an accurate formula for calculating the number of spanning trees when studying current networks,which is the famous matrix tree theorem.In this paper,we mainly use the complement of graphs and the product operation of various graphs(such as Cartesian product,normal product,tensor product,symmetric product,strong sum,composition product)to construct substituted graphs,and use the matrix tree theorem,the second kind of Chebyshev polynomials to study the number of spanning trees of these substituted graphs,and give their exact counting formulas.Specifically,first of all,we obtain the most important lemmas in this paper with the help of the second kind of Chebyshev polynomials.Secondly,taking the complete graph as the underlying graph of the substituted graph,the number of spanning trees of the substituted graph is studied when the complement graph of path and path,the complement graph of cycle and cycle are used as the base graph,respectively,and their exact counting formulas are given.Thirdly,taking the complete graph as the underlying graph of the substituted graph,the number of spanning trees of the substituted graph is studied when the graph of symmetric operation(such as Cartesian product,normal product,tensor product,symmetric product)is used as the base graph,and their exact counting formulas are given.Finally,taking the complete graph as the underlying graph of the substituted graph,the number of spanning trees of the substituted graph is syudied when the graph of asymmetric operation(such as strong sum,composition product)is used as the base graph,and their exact counting formulas are given.