Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  669.05046
Autor:  Alavi, Yousef; Boals, Alfred J.; Chartrand, Gary; Oellermann, Ortrud R.; Erdös, Paul
Title:  K-path irregular graphs. (In English)
Source:  Combinatorics, graph theory, and computing, Proc. 19th Southeast. Conf., Boca Raton/Fla. 1988, Congr. Numerantium 65, 201-210 (1988).
Review:  [For the entire collection see Zbl 665.00002.]
A connected graph G is k-path irregular, k \geq 1, if every two vertices of G that are connected by a path of length k have distinct degrees. This extends the concepts of highly irregular (or 2-path irregular) graphs and totally segregated (or 1-path irregular) graphs. Various sets S of positive integers are considered for which there exist k-path irregular graphs for every k in S. It is shown for every graph G and every odd positive integer k that G can be embedded as an induced subgraph in a k-path irregular graph. Some open problems are also stated.
Classif.:  * 05C38 Paths and cycles
                   05C99 Graph theory
Keywords:  k-path irregular graphs
Citations:  Zbl 665.00002

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page