اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAcyclic graphs with at least $2ell+1$ vertices are $ell$-recognizable
292
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
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 t
hat 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 wid
e 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
