Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn algebraic formulation of the graph reconstruction conjecture
113
0
0.0
(
0
)
Added by
Igor Carboni Oliveira
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck - the collection of its vertex-deleted subgraphs. Kocays Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph $G$ and any finite sequence of graphs, it gives a linear constraint that every reconstruction of $G$ must satisfy. Let $psi(n)$ be the number of distinct (mutually non-isomorphic) graphs on $n$ vertices, and let $d(n)$ be the number of distinct decks that can be constructed from these graphs. Then the difference $psi(n) - d(n)$ measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for $n$-vertex graphs if and only if $psi(n) = d(n)$. We give a framework based on Kocays lemma to study this discrepancy. We prove that if $M$ is a matrix of covering numbers of graphs by sequences of graphs, then $d(n) geq mathsf{rank}_mathbb{R}(M)$. In particular, all $n$-vertex graphs are reconstructible if one such matrix has rank $psi(n)$. To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix $M$ of covering numbers satisfies $d(n) = mathsf{rank}_mathbb{R}(M)$.
rate research
Read More
We consider three graphs, $G_{7,3}$, $G_{7,4}$, and $G_{7,6}$, related to Kellers conjecture in dimension 7. The conjecture is false for this dimension if and only if at least one of the graphs contains a clique of size $2^7 = 128$. We present an automated method to solve this conjecture by encoding the existence of such a clique as a propositional formula. We apply satisfiability solving combined with symmetry-breaking techniques to determine that no such clique exists. This result implies that every unit cube tiling of $mathbb{R}^7$ contains a facesharing pair of cubes. Since a faceshare-free unit cube tiling of $mathbb{R}^8$ exists (which we also verify), this completely resolves Kellers conjecture.
An oriented hypergraph is a hypergraph where each vertex-edge incidence is given a label of $+1$ or $-1$. We define the adjacency, incidence and Laplacian matrices of an oriented hypergraph and study each of them. We extend several matrix results known for graphs and signed graphs to oriented hypergraphs. New matrix results that are not direct generalizations are also presented. Finally, we study a new family of matrices that contains walk information.
A $k$-linear coloring of a graph $G$ is an edge coloring of $G$ with $k$ colors so that each color class forms a linear forest -- a forest whose each connected component is a path. The linear arboricity $chi_l(G)$ of $G$ is the minimum integer $k$ such that there exists a $k$-linear coloring of $G$. Akiyama, Exoo and Harary conjectured in 1980 that for every graph $G$, $chi_l(G)leq left lceil frac{Delta(G)+1}{2}rightrceil$ where $Delta(G)$ is the maximum degree of $G$. First, we prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture in some classes of graphs like cubic graphs and triangle-free planar graphs for which the conjecture was already known to be true. Next, for every 2-degenerate graph $G$, we show that $chi_l(G)=leftlceilfrac{Delta(G)}{2}rightrceil$ if $Delta(G)geq 5$. We conjecture that this equality holds also when $Delta(G)in{3,4}$ and show that this is the case for some well-known subclasses of 2-degenerate graphs. All our proofs can be converted into linear time algorithms.
We prove a conjecture of Ohba which says that every graph $G$ on at most $2chi(G)+1$ vertices satisfies $chi_ell(G)=chi(G)$.
Motivated by a hat guessing problem proposed by Iwasawa cite{Iwasawa10}, Butler and Graham cite{Butler11} made the following conjecture on the existence of certain way of marking the {em coordinate lines} in $[k]^n$: there exists a way to mark one point on each {em coordinate line} in $[k]^n$, so that every point in $[k]^n$ is marked exactly $a$ or $b$ times as long as the parameters $(a,b,n,k)$ satisfies that there are non-negative integers $s$ and $t$ such that $s+t = k^n$ and $as+bt = nk^{n-1}$. In this paper we prove this conjecture for any prime number $k$. Moreover, we prove the conjecture for the case when $a=0$ for general $k$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
