Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the maximal $alpha$-spectral radius of graphs with given matching number
124
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $mathscr{G}_{n,beta}$ be the set of graphs of order $n$ with given matching number $beta$. Let $D(G)$ be the diagonal matrix of the degrees of the graph $G$ and $A(G)$ be the adjacency matrix of the graph $G$. The largest eigenvalue of the nonnegative matrix $A_{alpha}(G)=alpha D(G)+A(G)$ is called the $alpha$-spectral radius of $G$. The graphs with maximal $alpha$-spectral radius in $mathscr{G}_{n,beta}$ are completely characterized in this paper. In this way we provide a general framework to attack the problem of extremal spectral radius in $mathscr{G}_{n,beta}$. More precisely, we generalize the known results on the maximal adjacency spectral radius in $mathscr{G}_{n,beta}$ and the signless Laplacian spectral radius.
rate research
Read More
A connected graph $G$ is a cactus if any two of its cycles have at most one common vertex. Let $ell_n^m$ be the set of cacti on $n$ vertices with matching number $m.$ S.C. Li and M.J. Zhang determined the unique graph with the maximum signless Laplacian spectral radius among all cacti in $ell_n^m$ with $n=2m$. In this paper, we characterize the case $ngeq 2m+1$. This confirms the conjecture of Li and Zhang(S.C. Li, M.J. Zhang, On the signless Laplacian index of cacti with a given number of pendant vetices, Linear Algebra Appl. 436, 2012, 4400--4411). Further, we characterize the unique graph with the maximum signless Laplacian spectral radius among all cacti on $n$ vertices.
Let $G$ be a simple graph with vertex set $V(G) = {v_1 ,v_2 ,cdots ,v_n}$. The Harary matrix $RD(G)$ of $G$, which is initially called the reciprocal distance matrix, is an $n times n$ matrix whose $(i,j)$-entry is equal to $frac{1}{d_{ij}}$ if $i ot=j$ and $0$ otherwise, where $d_{ij}$ is the distance of $v_i$ and $v_j$ in $G$. In this paper, we characterize graphs with maximum spectral radius of Harary matrix in three classes of simple connected graphs with $n$ vertices: graphs with fixed matching number, bipartite graphs with fixed matching number, and graphs with given number of cut edges, respectively.
Given a digraph $D$ with $m$ arcs and a bijection $tau: A(D)rightarrow {1, 2, ldots, m}$, we say $(D, tau)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and no two vertices in $D$ have the same vertex-sum under $tau$, where the vertex-sum of a vertex $u$ in $D$ under $tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. Hefetz, M{u}tze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs, biregular bipartite graphs, and graphs with large maximum degree. In this paper, we establish more evidence for the aforementioned conjecture by studying antimagic orientations of graphs $G$ with independence number at least $|V(G)|/2$ or at most four. We obtain several results. The method we develop in this paper may shed some light on attacking the aforementioned conjecture.
A graph is called radially maximal if it is not complete and the addition of any new edge decreases its radius. In 1976 Harary and Thomassen proved that the radius $r$ and diameter $d$ of any radially maximal graph satisfy $rle dle 2r-2.$ Dutton, Medidi and Brigham rediscovered this result with a different proof in 1995 and they posed the conjecture that the converse is true, that is, if $r$ and $d$ are positive integers satisfying $rle dle 2r-2,$ then there exists a radially maximal graph with radius $r$ and diameter $d.$ We prove this conjecture and a little more.
Determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvatal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear $3$-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of $3$-graphs with bounded codegree and matching number.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
