Premium
Large P 4 ‐free graphs with bounded degree
Author(s) -
Chung Myung S.,
West Douglas B.
Publication year - 1993
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.3190170111
Subject(s) - combinatorics , mathematics , induced subgraph , bipartite graph , degree (music) , bounded function , graph , discrete mathematics , vertex (graph theory) , mathematical analysis , physics , acoustics
Let ex * ( D ; H ) denote the maximum number of edges in a connected graph with maximum degree D and no induced subgraph isomorphic to H. We prove that this is finite only when H is a disjoint union of paths,m in which case we provide crude upper and lower bounds. When H is the four‐vertex path P 4 , we prove that the complete bipartite graph K D,D is the unique extremal graph. Furthermore, if G is a connected P 4 ‐free graph with maximum degree D and clique number ω, then G has at most D 2 − D (ω − 2)/2 edges. © 1993 John Wiley & Sons, Inc.
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