Alavi, Yousef; Boals, Alfred J.; Chartrand, Gary; Oellermann, Ortrud R.; Erdős, Paul K-path irregular graphs. (English) Zbl 0669.05046 Combinatorics, graph theory, and computing, Proc. 19th Southeast. Conf., Boca Raton/Fla. 1988, Congr. Numerantium 65, 201-210 (1988). [For the entire collection see Zbl 0665.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. Cited in 3 Documents MSC: 05C38 Paths and cycles 05C99 Graph theory Keywords:k-path irregular graphs Citations:Zbl 0665.00002 PDFBibTeX XML