Premium
Average Degree in Graph Powers
Author(s) -
DeVos Matt,
McDonald Jessica,
Scheide Diego
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21628
Subject(s) - mathematics , combinatorics , degree (music) , vertex (graph theory) , graph , simple graph , discrete mathematics , connectivity , physics , acoustics
The k th power of a simple graph G , denoted by G k , is the graph with vertex set V ( G ) where two vertices are adjacent if they are within distance k in G . We are interested in finding lower bounds on the average degree of G k . Here we prove that if G is connected with minimum degree d ≥ 2 and| V ( G ) | ≥ 8 3 d , then G 4 has average degree at least7 3 d . We also prove that if G is a connected d ‐regular graph on n vertices with diameter at least 3 k + 3 , then the average degree of G 3 k + 2is at least( 2 k + 1 ) ( d + 1 ) − k ( k + 1 )( d + 1 ) 2 / n − 1 .Both these results are shown to be essentially best possible; the second is best possible even when n / d is arbitrarily large.