Skip navigation
Skip navigation

Competition numbers, quasi-line graphs, and holes

McKay, Brendan; Schweitzer, Pascal; Schweitzer, Patrick


The competition graph of an acyclic directed graph D is the undirected graph on the same vertex set as D in which two distinct vertices are adjacent if they have a common out-neighbor in D. The competition number of an undirected graph G is the least number of isolated vertices that have to be added to G to make it the competition graph of an acyclic directed graph. We resolve two conjectures concerning competition graphs. First, we prove a conjecture of Opsut by showing that the competition...[Show more]

CollectionsANU Research Publications
Date published: 2014
Type: Journal article
Source: SIAM Journal on Discrete Mathematics
DOI: 10.1137/110856277


File Description SizeFormat Image
01_McKay_Competition_numbers,_2014.pdf25.73 kBAdobe PDF    Request a copy
02_McKay_Competition_numbers,_2014.pdf224.08 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator