Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn reconstruction of graphs from the multiset of subgraphs obtained by deleting $ell$ vertices
46
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
ErdH{o}s posed the problem of finding conditions on a graph $G$ that imply the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We generalize this problem to general cases. Let $delta_r$ be the least number so that any graph $G$ on $n$ vertices with minimum degree $delta_rn$ has the property $P_{r-1}(G)=K_rf(G),$ where $P_{r-1}(G)$ is the largest number of edges in an $(r-1)$-partite subgraph and $K_rf(G)$ is the largest number of edges in a $K_r$-free subgraph. We show that $frac{3r-4}{3r-1}<delta_rlefrac{4(3r-7)(r-1)+1}{4(r-2)(3r-4)}$ when $rge4.$ In particular, $delta_4le 0.9415.$
It is an intriguing question to see what kind of information on the structure of an oriented graph $D$ one can obtain if $D$ does not contain a fixed oriented graph $H$ as a subgraph. The related question in the unoriented case has been an active area of research, and is relatively well-understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs, and provide some results on the global behavior of the orientation of $D$. For the case that $H$ is an oriented four-cycle we prove: in every $H$-free oriented graph $D$, there is a pair $A,Bssq V(D)$ such that $e(A,B)ge e(D)^{2}/32|D|^{2}$ and $e(B,A)le e(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case $H$ is an oriented six-cycle, and a more precise result in the case $D$ is dense and $H$ is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph $D$, and provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.
Kuhn, Osthus and Taraz showed that for each gamma>0 there exists C such that any n-vertex graph with minimum degree gamma n contains a planar subgraph with at least 2n-C edges. We find the optimum value of C for all gamma<1/2 and sufficiently large n.
For a graph $G$, we associate a family of real symmetric matrices, $mathcal{S}(G)$, where for any $M in mathcal{S}(G)$, the location of the nonzero off-diagonal entries of $M$ are governed by the adjacency structure of $G$. The ordered multiplicity Inverse Eigenvalue Problem of a Graph (IEPG) is concerned with finding all attainable ordered lists of eigenvalue multiplicities for matrices in $mathcal{S}(G)$. For connected graphs of order six, we offer significant progress on the IEPG, as well as a complete solution to the ordered multiplicity IEPG. We also show that while $K_{m,n}$ with $min(m,n)ge 3$ attains a particular ordered multiplicity list, it cannot do so with arbitrary spectrum.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
