14 October 2013 in The Electronic Journal of Combinatorics
A graph $G$ is said to have a parity-linked orientation $\phi$ if every even cycle $C_{2k}$ in $G^{\phi}$ is evenly (resp. oddly) oriented whenever $k$ is even (resp. odd). In this paper, this concept is used to provide an affirmative answer to the following conjecture of D. Cui and Y. Hou [D. Cui, Y. Hou, On the skew spectra of Cartesian products of graphs, Electronic J. Combin. 20(2):#P19, 2013]: Let $G=G(X,Y)$ be a bipartite graph. Call the $X\rightarrow Y$ orientation of $G,$ the canonical orientation. Let $\phi$ be any orientation of $G$ and let $Sp_S(G^{\phi})$ and $Sp(G)$ denote respectively the skew spectrum of $G^{\phi}$ and the spectrum of $G.$ Then $Sp_S(G^{\phi}) = {\bf{i}} Sp(G)$ if and only if $\phi$ is switching-equivalent to the canonical orientation of $G.$ Using this result, we determine the switch for a special family of oriented hypercubes $Q_d^{\phi},$ $d\geq 1.$ Moreover, we give an orientation of the Cartesian product of a bipartite graph and a graph, and then determine the skew spectrum of the resulting oriented product graph, which generalizes a result of Cui and Hou. Further this can be used to construct new families of oriented graphs with maximum skew energy.
18 May 2012 in Graphs and Combinatorics
1 October 2020 in Acta Mathematicae Applicatae Sinica, English Series
6 June 2023 in Journal of Graph Theory
1 January 2019 in Complexity
The matching energy ME(G) of a graph G was introduced by Gutman and Wagner, which is defined as the sum of the absolute values of the roots of the matching polynomial m(G, x). The largest matching root λ1(G) is the largest root of the matching polynomial m(G, x). Let denote the complete r‐partite graph with order n = n1 + n2 + …+nr, where r > 1. In this paper, we prove that, for the given values n and r, both the matching energy ME(G) and the largest matching root λ1(G) of complete r‐partite graphs are minimal for complete split graph CS(n, r − 1) and are maximal for Turán graph T(n, r).