Premium
Local and global average degree in graphs and multigraphs
Author(s) -
Bertram E.,
Erds P.,
Horák P.,
Širáň J.,
Tuza Z. S.
Publication year - 1994
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.3190180702
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , degree (music) , simple graph , discrete mathematics , physics , acoustics
Abstract A vertex v of a graph G is called groupie if the average degree t v of all neighbors of v in G is not smaller than the average degree t G of G. Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the function f ( n ) = max min v ( t v / t G ), where the maximum ranges over all simple graphs on n vertices, and prove that f ( n ) = 1/42 n + o (1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degree t v is constant.