Research On Subgraph Counting

Graph counting problem has application value in many aspects,especially in the field of biology In graph theory,typical substructure counting problems include spanning tree counting problem,domination number problem and matching number problem However,for general graphs,the substructure counting problem of graphs is difficult,even NP complete Therefore,the study of subgraph counting with specific structural properties is of great significance This paper mainly studies the counting of subgraphs and the characterization of extreme graphs.In terms of subgraph counting,we determine the counting formula of all subgraphs with up to four edges and up to four points Two applications of subgraph counting are given.In the characterization of extreme graphs,we study the characterization of extreme graphs in bipartite graphs.Let G be a simple bipartite graph with order n,the adjacency matrix of G is recorded as A(G),and the characteristic polynomial of G is defined by where ai(G)is called the i-th adjacency coefficient of G.Denote by Bn,m the collection of all connected bipartite graphs having n vertices and m edges.A bipartite graph G is referred as 4-Sachs optimal if a4(G)=min{a4(H)|H?Bn,m}.We prove that every 4-sachs optimal bipartite graph is a difference graph,and derive some structural properties of 4-optimal bipartite graphs.Especially,we determine the unique 4-Sachs optimal bipartite graphs for n?5 and n-1?m?2(n-1).Finally,we provide a method to construct a class of non-isomorphic cospectral difference graphs,which denies Andelic's conjecture that there do not exist non-isomorphic cospectral difference graphs.