Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
distance; degree-continuous
distance; degree-continuous
Summary:
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)$.
References:
[ce:ia] G. Chartrand, L. Eroh, M. Schultz and P. Zhang: An introduction to analytic graph theory. Utilitas Math (to appear). MR 1832600
[cl:gd] G. Chartrand and L. Lesniak: Graphs & Digraphs, third edition. Chapman & Hall, New York, 1996. MR 1408678
[k:ug] D. König: Über Graphen und ihre Anwendung auf Determinantheorie und Mengenlehre. Math. Ann. 77 (1916), 453–465. DOI 10.1007/BF01456961 | MR 1511872
[s:ei] N. J. A. Sloane and S. Plouffe: The Encyclopedia of Integer Sequences. Academic Press, San Diego, 1995. MR 1327059
Search
Partner of
