On the Computation of the Competition Number of a Graph

DOI10.1137/0603043zbMath0512.05032OpenAlexW2091556347MaRDI QIDQ4750663

Robert J. Opsut

Publication date: 1982

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0603043

zbMATH Keywords

competition graphacyclic digraphclique covering numbercompetition number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99) Directed graphs (digraphs), tournaments (05C20)

Related Items (40)

Competition hypergraphs ⋮ A generalization of Opsut's lower bounds for the competition number of a graph ⋮ Competition numbers of graphs with a small number of triangles ⋮ Niche graphs ⋮ On the Competition Numbers of Diamond-Free Graphs ⋮ Edge-clique covers of the tensor product ⋮ Competition graphs of degree bounded digraphs ⋮ The competition numbers of complete multipartite graphs with many partite sets ⋮ The competition number of a graph and the dimension of its hole space ⋮ The competition number of a graph with exactly two holes ⋮ Competitively tight graphs ⋮ The competition number of the complement of a cycle ⋮ A generalization of Opsut's result on the competition numbers of line graphs ⋮ \((i,j)\) competition graphs ⋮ Competition numbers and phylogeny numbers: uniform complete multipartite graphs ⋮ Characterizations of competition multigraphs ⋮ Graphs having many holes but with small competition numbers ⋮ An upper bound for the competition numbers of graphs ⋮ Dimension-2 poset competition numbers and dimension-2 poset double competition numbers ⋮ The competition numbers of ternary Hamming graphs ⋮ Competition numbers of complete \(r\)-partite graphs ⋮ On Opsut's conjecture for hypercompetition numbers of hypergraphs ⋮ The elimination procedure for the competition number is not optimal ⋮ The competition number of a graph whose holes do not overlap much ⋮ The competition numbers of complete tripartite graphs ⋮ Phylogeny numbers ⋮ Note on the \(m\)-step competition numbers of paths and cycles ⋮ The competition number of a graph with exactly \(h\) holes, all of which are independent ⋮ Applications of edge coverings by cliques ⋮ A mathematical approach on representation of competitions: competition cluster hypergraphs ⋮ Phylogeny numbers of generalized Hamming graphs ⋮ The competition numbers of complete multipartite graphs and mutually orthogonal Latin squares ⋮ The \(m\)-step competition graph of a digraph ⋮ The competition numbers of Johnson graphs with diameter four ⋮ A characterization of competition graphs ⋮ A characterization of graphs of competition number m ⋮ A characterization of competition graphs of arbitrary digraphs ⋮ The \(m\)-step, same-step, and any-step competition graphs ⋮ The competition number of a graph having exactly one hole ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs

Cites Work

• Computing the boxicity of a graph by covering its complement by cointerval graphs
• A characterization of Robert's inequality for boxicity
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Computation of the Competition Number of a Graph