Premium
On minors of graphs with at least 3 n −4 edges
Author(s) -
Khalifat M.,
Politof Themistocles,
Satyanarayana A.
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.3190170409
Subject(s) - combinatorics , mathematics , graph , discrete mathematics , minor (academic) , law , political science
A point disconnecting set S of a graph G is a nontrivial m ‐separator, where m = | S |, if the connected components of G ‐ S can be partitioned into two subgraphs, each of which has at least two points. A 3‐connected graph is quasi 4‐connected if it has no nontrivial 3‐separators. Suppose G is a graph having n ≥ 6 points. We prove three results: (1) If G is quasi 4‐connected with at least 3 n ‐ 4 edges, then the graph K − 1 , obtained from K 6 by deleting an edge, is a minor of G. (2) If G has at least 3 n ‐ 4 edges then either K − 6 or the graph obtained by pasting two disjoint copies of K 5 together along a triangle is a minor of G. (3) If the minimum degree of G is at least 6, then K − 6 is a minor of G. © 1993 John Wiley & Sons, Inc.