Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
$F$-degree; $F$-degree continuous
$F$-degree; $F$-degree continuous
Summary:
For a nontrivial connected graph $F$, the $F$-degree of a vertex $v$ in a graph $G$ is the number of copies of $F$ in $G$ containing $v$. A graph $G$ is $F$-continuous (or $F$-degree continuous) if the $F$-degrees of every two adjacent vertices of $G$ differ by at most 1. All $P_3$-continuous graphs are determined. It is observed that if $G$ is a nontrivial connected graph that is $F$-continuous for all nontrivial connected graphs $F$, then either $G$ is regular or $G$ is a path. In the case of a 2-connected graph $F$, however, there always exists a regular graph that is not $F$-continuous. It is also shown that for every graph $H$ and every 2-connected graph $F$, there exists an $F$-continuous graph $G$ containing $H$ as an induced subgraph.
References:
[1] G. Chartrand, L. Eroh, M. Schultz and P. Zhang: An introduction to analytic graph theory. Utilitas Math (to appear). MR 1832600
[2] G. Chartrand, K. S. Holbert, O. R. Oellermann and H. C. Swart: $F$-degrees in graphs. Ars Combin. 24 (1987), 133–148. MR 0917968
[3] G. Chartrand and L. Lesniak: Graphs $\&$ Digraphs (third edition). Chapman $\&$ Hall, New York, 1996. MR 1408678
[4] P. Erdös and H. Sachs: Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss Z. Univ. Halle, Math-Nat. 12 (1963), 251–258. MR 0165515
[5] J. Gimbel and P. Zhang: Degree-continuous graphs. Czechoslovak Math. J (to appear). MR 1814641
[6] D. König: Über Graphen und ihre Anwendung auf Determinantheorie und Mengenlehre. Math. Ann. 77 (1916), 453–465. DOI 10.1007/BF01456961 | MR 1511872
Search
Partner of
