Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user3-Regular Graphs Are 2-Reconstructible
112
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
The 1-2-3 Conjecture, posed by Karo{n}ski, {L}uczak and Thomason, asked whether every connected graph $G$ different from $K_2$ can be 3-edge-weighted so that every two adjacent vertices of $G$ get distinct sums of incident weights. The 1-2 Conjecture states that if vertices also receive colors and the vertex color is added to the sum of its incident edges, then adjacent vertices can be distinguished using only ${ 1,2}$. In this paper we confirm 1-2 Conjecture for 3-regular graphs. Meanwhile, we show that every 3-regular graph can achieve a neighbor sum distinguishing edge coloring by using 4 colors, which answers 1-2-3 Conjecture positively.
A graph $G$ is total weight $(k,k)$-choosable if for any total list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and each edge $e$ a set $L(e)$ of $k$ real numbers, there is a proper total $L$-weighting, i.e., a mapping $f: V(G) cup E(G) to mathbb{R}$ such that for each $z in V(G) cup E(G)$, $f(z) in L(z)$, and for each edge $uv$ of $G$, $sum_{e in E(u)}f(e)+f(u) e sum_{e in E(v)}f(e) + f(v)$. This paper proves that if $G$ decomposes into complete graphs of odd order, then $G$ is total weight $(1,3)$-choosable. As a consequence, every Eulerian graph $G$ of large order and with minimum degree at least $0.91|V(G)|$ is total weight $(1,3)$-choosable. We also prove that any graph $G$ with minimum degree at least $0.999|V(G)|$ is total weight $(1,4)$-choosable.
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.
For any positive integers $n, s, t, l$ such that $n geq 10$, $s, t geq 2$, $l geq 1$ and $n geq s+t+l$, a new infinite family of regular 3-hypertopes with type $(2^s, 2^t, 2^l)$ and automorphism group of order $2^n$ is constructed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
