Degree-continuous graphs
Czechoslovak Mathematical Journal, Tome 51 (2001) no. 1, pp. 163-171
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library
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)$.
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)$.
@article{CMJ_2001_51_1_a14,
author = {Gimbel, John and Zhang, Ping},
title = {Degree-continuous graphs},
journal = {Czechoslovak Mathematical Journal},
pages = {163--171},
year = {2001},
volume = {51},
number = {1},
mrnumber = {1814641},
zbl = {1079.05504},
language = {en},
url = {http://geodesic.mathdoc.fr/item/CMJ_2001_51_1_a14/}
}
Gimbel, John; Zhang, Ping. Degree-continuous graphs. Czechoslovak Mathematical Journal, Tome 51 (2001) no. 1, pp. 163-171. http://geodesic.mathdoc.fr/item/CMJ_2001_51_1_a14/