Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDegree lists and connectedness are $3$-reconstructible for graphs with at least seven vertices
105
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The $k$-deck of a graph is the multiset of its subgraphs induced by $k$ vertices. A graph or graph property is $l$-reconstructible if it is determined by the deck of subgraphs obtained by deleting $l$ vertices. We show that the degree list of an $n$-vertex graph is $3$-reconstructible when $nge7$, and the threshold on $n$ is sharp. Using this result, we show that when $nge7$ the $(n-3)$-deck also determines whether an $n$-vertex graph is connected; this is also sharp. These results extend the results of Chernyak and Manvel, respectively, that the degree list and connectedness are $2$-reconstructible when $nge6$, which are also sharp.
rate research
Read More
A graph is $ell$-reconstructible if it is determined by its multiset of induced subgraphs obtained by deleting $ell$ vertices. We prove that $3$-regular graphs are $2$-reconstructible.
The $(n-ell)$-deck of an $n$-vertex graph is the multiset of subgraphs obtained from it by deleting $ell$ vertices. A family of $n$-vertex graphs is $ell$-recognizable if every graph having the same $(n-ell)$-deck as a graph in the family is also in the family. We prove that the family of $n$-vertex graphs having no cycles is $ell$-recognizable when $nge2ell+1$ (except for $(n,ell)=(5,2)$). It is known that this fails when $n=2ell$.
Let $G$ be an $n$-vertex graph and let $L:V(G)rightarrow P({1,2,3})$ be a list assignment over the vertices of $G$, where each vertex with list of size 3 and of degree at most 5 has at least three neighbors with lists of size 2. We can determine $L$-choosability of $G$ in $O(1.3196^{n_3+.5n_2})$ time, where $n_i$ is the number of vertices in $G$ with list of size $i$ for $iin {2,3}$. As a corollary, we conclude that the 3-colorability of any graph $G$ with minimum degree at least 6 can be determined in $O(1.3196^{n-.5Delta(G)})$ time.
Let $G$ be an $n$-vertex graph with the maximum degree $Delta$ and the minimum degree $delta$. We give algorithms with complexity $O(1.3158^{n-0.7~Delta(G)})$ and $O(1.32^{n-0.73~Delta(G)})$ that determines if $G$ is 3-colorable, when $delta(G)geq 8$ and $delta(G)geq 7$, respectively.
Koolen et al. showed that if a graph with smallest eigenvalue at least $-3$ has large minimal valency, then it is $2$-integrable. In this paper, we will focus on the sesqui-regular graphs with smallest eigenvalue at least $-3$ and study their integrability.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
