Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAcyclic graphs with at least $2ell+1$ vertices are $ell$-recognizable
292
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
In this paper, we show that all fat Hoffman graphs with smallest eigenvalue at least -1-tau, where tau is the golden ratio, can be described by a finite set of fat (-1-tau)-irreducible Hoffman graphs. In the terminology of Woo and Neumaier, we mean that every fat Hoffman graph with smallest eigenvalue at least -1-tau is an H-line graph, where H is the set of isomorphism classes of maximal fat (-1-tau)-irreducible Hoffman graphs. It turns out that there are 37 fat (-1-tau)-irreducible Hoffman graphs, up to isomorphism.
A graph is $(d_1, ..., d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, ..., V_r$ so that the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $iin {1, ..., r}$. For a given pair $(g, d_1)$, the question of determining the minimum $d_2=d_2(g; d_1)$ such that planar graphs with girth at least $g$ are $(d_1, d_2)$-colorable has attracted much interest. The finiteness of $d_2(g; d_1)$ was known for all cases except when $(g, d_1)=(5, 1)$. Montassier and Ochem explicitly asked if $d_2(5; 1)$ is finite. We answer this question in the affirmative with $d_2(5; 1)leq 10$; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$-colorable. Moreover, our proof extends to the statement that for any surface $S$ of Euler genus $gamma$, there exists a $K=K(gamma)$ where graphs with girth at least $5$ that are embeddable on $S$ are $(1, K)$-colorable. On the other hand, there is no finite $k$ where planar graphs (and thus embeddable on any surface) with girth at least $5$ are $(0, k)$-colorable.
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.
The Reconstruction Conjecture of Ulam asserts that, for $ngeq 3$, every $n$-vertex graph is determined by the multiset of its induced subgraphs with $n-1$ vertices. The conjecture is known to hold for various special classes of graphs but remains wide open. We survey results on the more general conjecture by Kelly from 1957 that for every positive integer $ell$ there exists $M_ell$ (with $M_1=3$) such that when $ngeq M_ell$ every $n$-vertex graph is determined by the multiset of its induced subgraphs with $n-ell$ vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
