Premium
Overlap number of graphs
Author(s) -
Cranston Daniel W.,
Korula Nitish,
LeSaulnier Timothy D.,
Milans Kevin G.,
Stocker Christopher J.,
Vandenbussche Jennifer,
West Douglas B.
Publication year - 2012
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.20596
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , bound graph , matching (statistics) , discrete mathematics , graph power , line graph , statistics
Abstract An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ( G ) (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If δ( G )⩾2 and G ≠ K 3 , then φ( G )⩽| E ( G )| − 1, with equality when G is connected and triangle‐free and has no star‐cutset. (3) If G is an n ‐vertex plane graph with n ⩾5, then φ( G )⩽2 n − 5, with equality when every face has length 4 and there is no star‐cutset. (4) If G is an n ‐vertex graph with n ⩾14, then φ( G )⩽ n 2 /4 − n /2 − 1, with equality for even n when G arises from K n /2, n /2 by deleting a perfect matching. © 2011 Wiley Periodicals, Inc. J Graph Theory