Let $G=(V,E)$ be a finite, simple, undirected graph. Let $\Delta(G)$ be the maximal degree of $G$. Is there a finite graph $G'=(V', E')$ with the following properties?
- $V\subseteq V'$,
- $E \subseteq E'$, and
- $G'$ is $\Delta(G)$-regular.
$\begingroup$
$\endgroup$
5
asked May 22, 2019 at 6:37
-
$\begingroup$ In other words, if $\Delta\ge d_1\ge d_2\ge\dots d_n\ge 0$, then $\Delta,\dots \Delta, d_1\dots d_n$ is a graphic sequence for some number of repetitions of $\Delta$. Looks obvious, doesn't it? $\endgroup$– fedjaCommented May 22, 2019 at 7:23
-
2$\begingroup$ @fedja not quite just graphic sequence, we should save the existed edges $\endgroup$– Fedor PetrovCommented May 22, 2019 at 7:29
-
$\begingroup$ @FedorPetrov $d_j$ are $\Delta$ minus the existing degrees, i.e., I'm looking for the complement. I thought that was clear enough :-) $\endgroup$– fedjaCommented May 22, 2019 at 7:31
-
1$\begingroup$ @fedja well, but the complement should avoid existed edges, right? $\endgroup$– Fedor PetrovCommented May 22, 2019 at 7:36
-
1$\begingroup$ @FedorPetrov Indeed, you are right. The correction is trivial (add some edges sticking out to saturate the existing vertices and consider the new graph), but then it basically becomes your construction. $\endgroup$– fedjaCommented May 22, 2019 at 7:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Yes. First of all, for any vertex $v\in V$ we draw the edges to $\Delta(G)-\deg(v)$ new vertices so that the degree of $v$ becomes equal to $\Delta(G)$. Now all degrees are equal either to $\Delta(G)$ or to 1. Without loss of generality, the number of vertices with degree 1 is even (else add the disjoint copy of the current graph). Partition them onto pairs, and for any pair $a,b$ take a graph $K_{d+1}\setminus \{ab\}$ on the vertex set $\{a,b, d-1\, \text{new vertices}\}$.
answered May 22, 2019 at 7:27
-
$\begingroup$ Very nice construction, thanks Fedor! $\endgroup$ Commented May 22, 2019 at 7:30