On bi-regular graphs determined by their generalized characteristic polynomials (Q1940102)

It was shown that whether a graph \(G\) is determined by its generalized characteristic polynomial is equivalent to the same problem for a well defined bi-regular graph \(\widehat G\). A unified approach is proposed to show that some new families of bi-regular graphs are characterized by their generalized characteristic polynomials. The authors consider obviously only simple graphs. Here for a given graph \(G = (V,E)\) with adjacency matrix \(A_G\) and the degree diagonal matrix \(D_G\), \(\phi_G(\lambda,t) = \det(\lambda I-(A_G-tD_G))\). It generalizes characteristic polynomials like polynomials of \(A\), \(L\) and \(Q\). Its combinatorial interpretation is an equivalent to the Bartholdi zeta function. The paper mainly extends the results of W. Hall, the notions of cospectral graphs, DS claiming their results as: Whereas on a very narrow family of graphs -- bi-regular are focused, yet it should not be taken that it is a serious type of restriction for any graph \(G\) to be determined by \(\phi_G\) iff the corresponding bi-regular graph \(\widehat G\) is determined by \(\phi(\widehat G)\). A unified approach is given for constructing large \(\phi\)-DS graph from smaller ones. Further it is presented more non trivial families of bi-regular graphs that are determined by their generalized characteristic polynomials. The rest contains the following: For any graph \(G\), whether \(G\) is determined by \(\phi(G)\) can be reduced to whether the corresponding bi-regular graph \(\widehat G\) is determined by \(\phi(\widehat G)\). Another unified approach for constructing graphs \(G\) is presented that are determined by \(\phi_G\). Some more families of graphs are given that are determined by \(\phi_G\). Excluding some basic lemmas the authors state result of Wang et al. (If \(\phi(G) = \phi(H)\), then graphs \(G\) and \(H\) have the same degree sequence.) and prove the following: {\parindent=6mm \begin{itemize}\item[1)]Let \(G\) and \(H\) be two bi-regular graphs with \(\phi_G= \phi_H\), and let the vertex partition of \(G\) and \(H\) be defined as above. Then the induced graphs \(G[V_i]\) and \(H[V_i']\) are cospectral, for \(i=1,2\). \item[2)]Let \(G\) and \(H\) be two graphs. Then \(G\) and \(H\) are \(\phi\)-cospectral if and if \(\widehat G\) and \(\widehat H\) are \(\phi\)-cospectral. \item[3)]\(G\) is \(\phi\)-DS if and only if \(\widehat G\) is \(\phi\)-DS. \end{itemize}} Section 2 provides a unified approach for showing that some families of bi-regular graphs are \(\phi\)-DS, through graph operations. It is noted that under a mild restriction the sum (resp. product) of two A-DS regular graph is \(\phi\)-DS. It is remarked that the above result is generally not true for a single kind spectrum. Another result does not require both graphs in the product to be regular. One of them can be a bi-regular graph. {\parindent=6mm \begin{itemize}\item[i)]Let \(\Gamma\) be a \(d\)-regular graph of \(m\). Let \(\Gamma_i\) be a bi-regular graph of order \(n_i\) with degree \(r^{k_i}\), \((r-m)^{n_i-k_i}\) (\(r\geq m)\), for \(i=1,\dots,s\). Let \(G\) be the graph obtained from the disjoint union \(\Gamma\cup \left(\bigcup_{i=1}^s\Gamma_i\right)\) by connecting each vertex of \(\Gamma\) and \(\bigcup_{i=1}^s\Gamma_i\) are A-DS. If \(G\) is non singular, then \(G\) is \(\phi\)-DS. The authors present more families of bi-regular \(\phi\)-DS graphs for the illustration of their methods. For this purpose, some more definitions are included such as generalized \(\Theta\)-graph, \(\Theta'\)-graph, graph \(T_1 (l_1 , l_2 , l_3 )\), \(T_2 (l_1 , l_2 , l_3 )\), \(T_3 (l_1 , l_2 , l_3 )\). It is shown that the sun-graph is \(\phi\)-DS. A short proof of a weaker result is communicated in connection with Mirzakhah et al. (the sun graph is determined by its signless spectrum) one \(\phi\)-DS property is incorporated viz., the number of spanning trees is determined by the L-spectrum. \item[ii)]the generalized \(\Theta\)-graph , the graphs \(T_1 (l_1 , l_2 , l_3 )\), \(T_2 (l_1 , l_2 , l_3 )\) and \(T_3 (l_1 , l_2 , l_3 )\) are all \(\phi\)-DS. \end{itemize}} It is shown that \(G\) is \(\phi\)-DS iff the corresponding bi-degree graph \(\widehat G\) is \(\phi\)-DS -- thus reducing the original problem of determining whether a graph is \(\phi\)-DS to the same problem for a very narrow family of graph bi-degreed graphs. Finally the authors' suggestion: Here only considered some specific bi-regular graphs so far. It would be an interesting future work to further this line of research by considering more-bi-regular graphs.