Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Q-index and connectivity of graphs
244
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A connected graph $G$ is said to be $k$-connected if it has more than $k$ vertices and remains connected whenever fewer than $k$ vertices are deleted. In this paper, for a connected graph $G$ with sufficiently large order, we present a tight sufficient condition for $G$ with fixed minimum degree to be $k$-connected based on the $Q$-index. Our result can be viewed as a spectral counterpart of the corresponding Dirac type condition.
rate research
Read More
Let $G$ be a nonempty simple graph with a vertex set $V(G)$ and an edge set $E(G)$. For every injective vertex labeling $f:V(G)tomathbb{Z}$, there are two induced edge labelings, namely $f^+:E(G)tomathbb{Z}$ defined by $f^+(uv)=f(u)+f(v)$, and $f^-:E(G)tomathbb{Z}$ defined by $f^-(uv)=|f(u)-f(v)|$. The sum index and the difference index are the minimum cardinalities of the ranges of $f^+$ and $f^-$, respectively. We provide upper and lower bounds on the sum index and difference index, and determine the sum index and difference index of various families of graphs. We also provide an interesting conjecture relating the sum index and the difference index of graphs.
The cut-rank of a set $X$ in a graph $G$ is the rank of the $Xtimes (V(G)-X)$ submatrix of the adjacency matrix over the binary field. A split is a partition of the vertex set into two sets $(X,Y)$ such that the cut-rank of $X$ is less than $2$ and both $X$ and $Y$ have at least two vertices. A graph is prime (with respect to the split decomposition) if it is connected and has no splits. A graph $G$ is $k^{+ell}$-rank-connected if for every set $X$ of vertices with the cut-rank less than $k$, $lvert Xrvert$ or $lvert V(G)-Xrvert $ is less than $k+ell$. We prove that every prime $3^{+2}$-rank-connected graph $G$ with at least $10$ vertices has a prime $3^{+3}$-rank-connected pivot-minor $H$ such that $lvert V(H)rvert =lvert V(G)rvert -1$. As a corollary, we show that every excluded pivot-minor for the class of graphs of rank-width at most $k$ has at most $(3.5 cdot 6^{k}-1)/5$ vertices for $kge 2$. We also show that the excluded pivot-minors for the class of graphs of rank-width at most $2$ have at most $16$ vertices.
Let $G$ be a finite simple non-complete connected graph on ${1, ldots, n}$ and $kappa(G) geq 1$ its vertex connectivity. Let $f(G)$ denote the number of free vertices of $G$ and $mathrm{diam}(G)$ the diameter of $G$. Being motivated by the computation of the depth of the binomial edge ideal of $G$, the possible sequences $(n, q, f, d)$ of integers for which there is a finite simple non-complete connected graph $G$ on ${1, ldots, n}$ with $q = kappa(G), f = f(G), d = mathrm{diam}(G)$ satisfying $f + d = n + 2 - q$ will be determined. Furthermore, finite simple non-complete connected graphs $G$ on ${1, ldots, n}$ satisfying $f(G) + mathrm{diam}(G) = n + 2 - kappa(G)$ will be classified.
Let $Sz(G),Sz^*(G)$ and $W(G)$ be the Szeged index, revised Szeged index and Wiener index of a graph $G.$ In this paper, the graphs with the fourth, fifth, sixth and seventh largest Wiener indices among all unicyclic graphs of order $ngeqslant 10$ are characterized; as well the graphs with the first, second, third, and fourth largest Wiener indices among all bicyclic graphs are identified. Based on these results, further relation on the quotients between the (revised) Szeged index and the Wiener index are studied. Sharp lower bound on $Sz(G)/W(G)$ is determined for all connected graphs each of which contains at least one non-complete block. As well the connected graph with the second smallest value on $Sz^*(G)/W(G)$ is identified for $G$ containing at least one cycle.
In this paper we study a pair of numerical parameters associated to a graph $G$. One the one hand, one can construct $text{Hom}(K_2, G)$, a space of homomorphisms from a edge $K_2$ into $G$ and study its (topological) connectivity. This approach dates back to the neighborhood complexes introduced by Lovasz in his proof of the Kneser conjecture. In another direction Brightwell and Winkler introduced a graph parameter called the warmth $zeta(G)$ of a graph $G$, based on asymptotic behavior of $d$-branching walks in $G$ and inspired by constructions in statistical physics. Both the warmth of $G$ and the connectivity of $text{Hom}(K_2,G)$ provide lower bounds on the chromatic number of $G$. Here we seek to relate these two constructions, and in particular we provide evidence for the conjecture that the warmth of a graph $G$ is always less than three plus the connectivity of $text{Hom}(K_2, G)$. We succeed in establishing a first nontrivial case of the conjecture, by showing that $zeta(G) leq 3$ if $text{Hom}(K_2,G)$ has an infinite first homology group. We also calculate warmth for a family of `twisted toroidal graphs that are important extremal examples in the context of $text{Hom}$ complexes. Finally we show that $zeta(G) leq n-1$ if a graph $G$ does not have the complete bipartite graph $K_{a,b}$ for $a+b=n$. This provides an analogue for a similar result in the context of $text{Hom}$ complexes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
