Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe strong spectral property for graphs
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We introduce the set $mathcal{G}^{rm SSP}$ of all simple graphs $G$ with the property that each symmetric matrix corresponding to a graph $G in mathcal{G}^{rm SSP}$ has the strong spectral property. We find several families of graphs in $mathcal{G}^{rm SSP}$ and, in particular, characterise the trees in $mathcal{G}^{rm SSP}$.
rate research
Read More
Let $H$ be connected $m$-uniform hypergraph and $mathcal{A}(H)$ be the adjacency tensor of $H$. The stabilizing index of $H$, denoted by $s(H)$, is exactly the number of eigenvectors of $mathcal{A}(H)$ associated with the spectral radius, and the cyclic index of $H$, denoted by $c(H)$, is the number of eigenvalues of $mathcal{A}(H)$ with modulus equal to the spectral radius. Let $bar{H}$ be a $k$-fold covering of $H$. Then $bar{H}$ is isomorphic to a hypergraph $H_B^phi$ derived from the incidence graph $B_H$ of $H$ together with a permutation voltage assignment $phi$ in the symmetric group $mathbb{S}_k$. In this paper, we first characterize the connectedness of $bar{H}$ by using $H_B^phi$ for subsequent discussion. By applying the theory of module and group representation, we prove that if $bar{H}$ is connected, then $s(H) mid s(bar{H})$ and $c(H) mid c(bar{H})$. In the situation that $bar{H}$ is a $2$-fold covering of $H$, if $m$ is even, we show that regardless of multiplicities, the spectrum of $mathcal{A}(bar{H})$ contains the spectrum of $mathcal{A}(H)$ and the spectrum of a signed hypergraph constructed from $H$ and the covering projection; if $m$ is odd, we give an explicit formula for $s(bar{H})$.
We prove that there exists a function $f(k)=mathcal{O}(k^2 log k)$ such that for every $C_4$-free graph $G$ and every $k in mathbb{N}$, $G$ either contains $k$ vertex-disjoint holes of length at least $6$, or a set $X$ of at most $f(k)$ vertices such that $G-X$ has no hole of length at least $6$. This answers a question of Kim and Kwon [ErdH{o}s-Posa property of chordless cycles and its applications. JCTB 2020].
In 1972, Tutte posed the $3$-Flow Conjecture: that all $4$-edge-connected graphs have a nowhere zero $3$-flow. This was extended by Jaeger et al.(1992) to allow vertices to have a prescribed, possibly non-zero difference (modulo $3$) between the inflow and outflow. They conjectured that all $5$-edge-connected graphs with a valid prescription function have a nowhere zero $3$-flow meeting that prescription. Kochol (2001) showed that replacing $4$-edge-connected with $5$-edge-connected would suffice to prove the $3$-Flow Conjecture and Lovasz et al.(2013) showed that both conjectures hold if the edge connectivity condition is relaxed to $6$-edge-connected. Both problems are still open for $5$-edge-connected graphs. The $3$-Flow Conjecture was known to hold for planar graphs, as it is the dual of Grotzschs Colouring Theorem. Steinberg and Younger (1989) provided the first direct proof using flows for planar graphs, as well as a proof for projective planar graphs. Richter et al.(2016) provided the first direct proof using flows of the Strong $3$-Flow Conjecture for planar graphs. We prove the Strong $3$-Flow Conjecture for projective planar graphs.
For an ordered subset $S = {s_1, s_2,dots s_k}$ of vertices and a vertex $u$ in a connected graph $G$, the metric representation of $u$ with respect to $S$ is the ordered $k$-tuple $ r(u|S)=(d_G(v,s_1), d_G(v,s_2),dots,$ $d_G(v,s_k))$, where $d_G(x,y)$ represents the distance between the vertices $x$ and $y$. The set $S$ is a metric generator for $G$ if every two different vertices of $G$ have distinct metric representations. A minimum metric generator is called a metric basis for $G$ and its cardinality, $dim(G)$, the metric dimension of $G$. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs.
We establish mild conditions under which a possibly irregular, sparse graph $G$ has many strong orientations. Given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ satisfies a minimum degree condition of $(1+c_1)log_2{n}$ and has Cheeger constant at least $c_2frac{log_2log_2{n}}{log_2{n}}$, then the resulting randomly oriented directed graph is strongly connected with high probability. This Cheeger constant bound can be replaced by an analogous spectral condition via the Cheeger inequality. Additionally, we provide an explicit construction to show our minimum degree condition is tight while the Cheeger constant bound is tight up to a $log_2log_2{n}$ factor.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
