Premium
A property of trees in terms of unique connected subgraphs
Author(s) -
Hedetniemi Stephen T.,
Spresser Diane M.
Publication year - 1977
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.3190010409
Subject(s) - mathematics , combinatorics , graph , distance hereditary graph , induced subgraph , property (philosophy) , vertex connectivity , tree (set theory) , discrete mathematics , line graph , graph power , vertex (graph theory) , philosophy , epistemology
The following theorem is proved: Let G be a graph with p ≥ 3 points such that for some n , 3 ≤ n ≤ p , any n points lie on a unique smallest connected subgraph. Then G = C n +1 or G is a tree, and conversely.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom