Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWarmth and connectivity of neighborhood complexes of graphs
121
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The paper studies the connectivity properties of facet graphs of simplicial complexes of combinatorial interest. In particular, it is shown that the facet graphs of $d$-cycles, $d$-hypertrees and $d$-hypercuts are, respectively, $(d+1)$, $d$, and $(n-d-1)$-vertex-connected. It is also shown that the facet graph of a $d$-cycle cannot be split into more than $s$ connected components by removing at most $s$ vertices. In addition, the paper discusses various related issues, as well as an extension to cell-complexes.
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.
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.
The notion of $times$-homotopy from cite{DocHom} is investigated in the context of the category of pointed graphs. The main result is a long exact sequence that relates the higher homotopy groups of the space $Hom_*(G,H)$ with the homotopy groups of $Hom_*(G,H^I)$. Here $Hom_*(G,H)$ is a space which parametrizes pointed graph maps from $G$ to $H$ (a pointed version of the usual $Hom$ complex), and $H^I$ is the graph of based paths in $H$. As a corollary it is shown that $pi_i big(Hom_*(G,H) big) cong [G,Omega^i H]_{times}$, where $Omega H$ is the graph of based closed paths in $H$ and $[G,K]_{times}$ is the set of $times$-homotopy classes of pointed graph maps from $G$ to $K$. This is similar in spirit to the results of cite{BBLL}, where the authors seek a space whose homotopy groups encode a similarly defined homotopy theory for graphs. The categorical connections to those constructions are discussed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
