| Title:
|
Degree-continuous graphs (English) |
| Author:
|
Gimbel, John |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
51 |
| Issue:
|
1 |
| Year:
|
2001 |
| Pages:
|
163-171 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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)$. (English) |
| Keyword:
|
distance |
| Keyword:
|
degree-continuous |
| MSC:
|
05C07 |
| MSC:
|
05C12 |
| idZBL:
|
Zbl 1079.05504 |
| idMR:
|
MR1814641 |
| . |
| Date available:
|
2009-09-24T10:40:57Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127635 |
| . |
| Reference:
|
[ce:ia] G. Chartrand, L. Eroh, M. Schultz and P. Zhang: An introduction to analytic graph theory.Utilitas Math (to appear). MR 1832600 |
| Reference:
|
[cl:gd] G. Chartrand and L. Lesniak: Graphs & Digraphs, third edition.Chapman & Hall, New York, 1996. MR 1408678 |
| Reference:
|
[k:ug] D. König: Über Graphen und ihre Anwendung auf Determinantheorie und Mengenlehre.Math. Ann. 77 (1916), 453–465. MR 1511872, 10.1007/BF01456961 |
| Reference:
|
[s:ei] N. J. A. Sloane and S. Plouffe: The Encyclopedia of Integer Sequences.Academic Press, San Diego, 1995. MR 1327059 |
| . |
