Degree-continuous graphs

Gimbel, John ; Zhang, Ping

Czechoslovak Mathematical Journal, Tome 51 (2001) no. 1, pp. 163-171.

Résumé

A graph $G$ is degree-continuous if the degrees of every two adjacent vertices of $G$ differ by at most 1. A finite nonempty set $S$ of integers is convex if $k \in S$ for every integer $k$ with $\min (S) \le k \le \max (S)$. It is shown that for all integers $r > 0$ and $s \ge 0$ and a convex set $S$ with $\min (S) = r$ and $\max (S) = r+s$, there exists a connected degree-continuous graph $G$ with the degree set $S$ and diameter $2s+2$. The minimum order of a degree-continuous graph with a prescribed degree set is studied. Furthermore, it is shown that for every graph $G$ and convex set $S$ of positive integers containing the integer 2, there exists a connected degree-continuous graph $H$ with the degree set $S$ and containing $G$ as an induced subgraph if and only if $\max (S)\ge \Delta (G)$ and $G$ contains no $r-$regular component where $r = \max (S)$.

Détail

Classification : 05C07, 05C12
Keywords: distance; degree-continuous