A simple connected nonregular graph is said to be $(\Delta,\delta)$-bidegreed, or biregular, if the vertices have degree from the set $\{\Delta,\delta\}$, with $\Delta>\delta$. We consider two classes of $(\Delta,1)$-bidegreed graphs denoted by $\Theta(n,\Delta,k)$ and $\mathcal{C}(n,\Delta,k)$. A graph belongs to $\Theta(n,\Delta,k)$ if: a) it is obtained from $k\geq3$ disjoint paths $P_i=[u_i,\ldots,v_i]$, $i=1,2,\ldots,k$, by identifying the vertices $u_1,u_2,\ldots,u_k$ and the vertices $v_1,v_2,\ldots,v_k$, and the graph so obtained has $n$ vertices; b) for each of the $n$ vertices, pendant vertices are added, so that any vertex from any $P_i$ has degree $\Delta\geq k$. The class $\mathcal{C}(n,\Delta,k)$, $k\geq 2$, is similarly obtained by identifying all the vertices $u_1,u_2,\ldots,u_k$ and $v_1,v_2,\ldots,v_k$ from the $P_i$'s, into a single vertex. In this paper we show that for any graph in $\Theta(n,\Delta,k)$ or $\mathcal{C}(n,\Delta,k)$, the spectral radius of the adjacency matrix increases whenever the difference between the lengths of any two $P_i$'s increases. We also compute some bounds for the spectral radius when the lengths of the $P_i$'s tend to infinity. Finally we discuss about bicyclic $(\Delta,1)$-bidegreed graphs with $n$ degree $\Delta$ vertices minimizing the spectral radius. We prove that in most cases such graphs do not belong to $\mathcal{C}(n,\Delta,2)$.
On the largest eigenvalue of some bidegreed graphs
BELARDO, FRANCESCO
2015-01-01
Abstract
A simple connected nonregular graph is said to be $(\Delta,\delta)$-bidegreed, or biregular, if the vertices have degree from the set $\{\Delta,\delta\}$, with $\Delta>\delta$. We consider two classes of $(\Delta,1)$-bidegreed graphs denoted by $\Theta(n,\Delta,k)$ and $\mathcal{C}(n,\Delta,k)$. A graph belongs to $\Theta(n,\Delta,k)$ if: a) it is obtained from $k\geq3$ disjoint paths $P_i=[u_i,\ldots,v_i]$, $i=1,2,\ldots,k$, by identifying the vertices $u_1,u_2,\ldots,u_k$ and the vertices $v_1,v_2,\ldots,v_k$, and the graph so obtained has $n$ vertices; b) for each of the $n$ vertices, pendant vertices are added, so that any vertex from any $P_i$ has degree $\Delta\geq k$. The class $\mathcal{C}(n,\Delta,k)$, $k\geq 2$, is similarly obtained by identifying all the vertices $u_1,u_2,\ldots,u_k$ and $v_1,v_2,\ldots,v_k$ from the $P_i$'s, into a single vertex. In this paper we show that for any graph in $\Theta(n,\Delta,k)$ or $\mathcal{C}(n,\Delta,k)$, the spectral radius of the adjacency matrix increases whenever the difference between the lengths of any two $P_i$'s increases. We also compute some bounds for the spectral radius when the lengths of the $P_i$'s tend to infinity. Finally we discuss about bicyclic $(\Delta,1)$-bidegreed graphs with $n$ degree $\Delta$ vertices minimizing the spectral radius. We prove that in most cases such graphs do not belong to $\mathcal{C}(n,\Delta,2)$.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.