A graph $G$ is said to have a parity-linked orientation $\phi$ if every even cycle $C_{2k}$ in $G^{\phi}$ evenly (resp. oddly) oriented whenever $k$ odd). In this paper, concept used provide an affirmative answer the following conjecture of D. Cui and Y. Hou [D. Cui, Hou, On skew spectra Cartesian products graphs, Electronic J. Combin. 20(2):#P19, 2013]: Let $G=G(X,Y)$ be bipartite graph. Call $X\rightarrow Y$ $G,$ canonical orientation. any let $Sp_S(G^{\phi})$ $Sp(G)$ denote respectively...

Let $G$ be a simple undirected graph with adjacency matrix $A(G)$. The energy of is defined as the sum absolute values all eigenvalues $A(G)$, which was introduced by Gutman in 1970s. Since has important chemical applications, it causes great concern and many generalizations. skew energy-like are generalizations oriented graphs. $G^σ$ an $S(G^σ)$. $G^σ$, denoted $\mathcal{E}_S(G^σ)$, norms $S(G^σ)$, Adiga, Balakrishnan So 2010. In this paper, we summarize main results on Some open problems...

Let $G$ be a simple graph with no even cycle, called an odd-cycle graph. Cavers et al. [Linear Algebra Appl. 436(12):4512-1829, 2012] showed that the spectral radius of $G^\sigma$ is same for every orientation $\sigma$ $G$, and equals maximum matching root $G$. They proposed conjecture graphs which attain skew among order $n$ are isomorphic to one vertex degree $n-1$ size $m=\lfloor 3(n-1)/2\rfloor$. By using Kelmans transformation, we give proof conjecture. Moreover, sharp upper bounds...

‎‎Given a graph $G$‎, ‎let $G^sigma$ be an oriented of $G$ with‎ ‎the orientation $sigma$ and skew-adjacency matrix $S(G^sigma)$‎. ‎Then the spectrum $S(G^sigma)$ consisting all eigenvalues of‎ ‎$S(G^sigma)$ is called skew-spectrum $G^sigma$‎, ‎denoted by‎ ‎$Sp(G^sigma)$‎. ‎The skew energy by $mathcal{E}_S(G^sigma)$‎, ‎is defined as sum the‎ ‎norms ‎In this paper‎, ‎we give orientations Kronecker product $Hotimes G$ strong‎ ‎product $Hast $H$ where bipartite $G$‎ arbitrary graph‎. we...

Abstract The mean subtree order of a graph is the number vertices all subtrees this divided by graph. In 2021, Cameron and Mol constructed special proved that addition single edge between pair nonadjacent in can decrease as much when large enough. Moreover, they left conjecture for every positive integer , there exists obtained adding edges to another then more than . paper, we confirm conjecture.

The \emph{spanning tree packing number} of a graph $G$ is the maximum number edge-disjoint spanning trees contained in $G$. Let $k\geq 1$ be fixed integer. Palmer and Spencer proved that almost every random process, hitting time for having $k$ equals minimum degree $k$. In this paper, we prove any $p$ such $(\log n+ω(1))/n\leq p\leq (1.1\log n)/n$, surely $G(n,p)$ satisfies equal to degree. Note bound will allow function $n$, sense improve result Spencer. Moreover, also obtain $p\geq (51\log...

Let $G$ be a graph with maximum degree $Δ$, and let $G^σ$ an oriented of skew adjacency matrix $S(G^σ)$. The spectral radius $ρ_s(G^σ)$ is defined as the has been studied, but only few results about its lower bound are known. This paper determines some bounds radius, then studies graphs whose radii attain $\sqrtΔ$. Moreover, we apply to energy graphs, which sum norms all eigenvalues $S(G^σ)$, denoted by $\mathcal{E}_s(G^σ)$. As results, obtain energy, improve known obtained Adiga et al.

The matching energy of a graph was introduced by Gutman and Wagner, which is defined as the sum absolute values roots polynomial graph. For random $G_{n,p}$ order $n$ with fixed probability $p\in (0,1)$, Wagner [I. Gutman, S. graph, Discrete Appl. Math. 160(2012), 2177--2187] proposed conjecture that converges to $\frac{8\sqrt{p}}{3π}n^{\frac{3}{2}}$ almost surely. In this paper, using analysis method, we prove true.

Let $G$ be a simple undirected graph, and $G^\sigma$ an oriented graph of with the orientation $\sigma$ skew-adjacency matrix $S(G^\sigma)$. The skew energy $G^\sigma$, denoted by $\mathcal{E}_S(G^\sigma)$, is defined as sum absolute values all eigenvalues In this paper, we characterize underlying graphs 4-regular optimum give orientations these such that resultant indeed attain optimum. It should pointed out there are infinitely many connected graphs, while 3-regular case only has two...

The matching energy M E ( G ) of a graph was introduced by Gutman and Wagner, which is defined as the sum absolute values roots polynomial m , x ). largest root λ 1 Let denote complete r ‐partite with order n = + 2 …+ where > 1. In this paper, we prove that, for given both graphs are minimal split C S − 1) maximal Turán T

Let $G$ be a simple graph with no even cycle, called an odd-cycle graph. Cavers et al. [Cavers Skew-adjacency matrices of graphs, Linear Algebra Appl. 436(2012), 4512--1829] showed that the spectral radius $G^\sigma$ is same for every orientation $\sigma$ $G$, and equals maximum matching root $G$. They proposed conjecture graphs which attain skew among order $n$ are isomorphic to one vertex degree $n-1$ size $m=\lfloor 3(n-1)/2\rfloor$. This paper, by using Kelmans transformation, gives...

Given a graph $G$, let $G^\sigma$ be an oriented of $G$ with the orientation $\sigma$ and skew-adjacency matrix $S(G^\sigma)$. The skew energy $G^\sigma$, denoted by $\mathcal{E}_S(G^\sigma)$, is defined as sum absolute values all eigenvalues In this paper, we study random graphs formulate exact estimate for almost generalizing Wigner's semicircle law. Moreover, consider regular $G_{n,d}^\sigma$, get graphs.

A vertex-colored graph $G$ is {\it rainbow vertex-connected} if any pair of vertices in are connected by a path whose internal have distinct colors, which was introduced Krivelevich and Yuster. The vertex-connection number} $G$, denoted $rvc(G)$, the smallest number colors that needed order to make vertex-connected. In previous paper we showed it NP-Complete decide whether given has $rvc(G)=2$. this show for every integer $k\geq 2$, deciding $rvc(G)\leq k$ NP-Hard. We also fixed problem...

Given a graph $G$, let $G^σ$ be an oriented of $G$ with the orientation $σ$ and skew-adjacency matrix $S(G^σ)$. Then spectrum $S(G^σ)$ is called skew-spectrum $G^σ$, denoted by $Sp_S(G^σ)$. It known that bipartite if only there such $Sp_S(G^σ)=iSp(G)$. In [D. Cui, Y. Hou, On skew spectra Cartesian products graphs, Electron. J. Combin. 20(2013), #P19], Cui Hou conjectured unique under switching-equivalence. this paper, we prove conjecture true. Moreover, give product graph, then determine...