On the Computation of the Competition Number of a Graph

DOI10.1137/0603043MaRDI QIDQ4750663zbMATH OpenOpenAlexFDO

Authors 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

acyclic digraphclique covering numbercompetition graphcompetition number

Mathematics Subject Classification ID

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

Cites work

• A characterization of Robert's inequality for boxicity
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 3606214 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 638670 (Why is no real title available?)
• scientific article; zbMATH DE number 3226832 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)

Cited in

(40)

• The competition numbers of complete tripartite graphs
• 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
• The competition numbers of complete multipartite graphs and mutually orthogonal Latin squares
• A characterization of competition graphs
• A characterization of graphs of competition number m
• A characterization of competition graphs of arbitrary digraphs
• Niche graphs
• \((i,j)\) competition graphs
• Phylogeny numbers
• Competition numbers of graphs with a small number of triangles
• The \(m\)-step competition graph of a digraph
• Competition hypergraphs
• Competition numbers and phylogeny numbers: uniform complete multipartite graphs
• Phylogeny numbers of generalized Hamming graphs
• Competitively tight graphs
• The competition number of the complement of a cycle
• The elimination procedure for the competition number is not optimal
• The \(m\)-step, same-step, and any-step competition graphs
• The competition number of a graph having exactly one hole
• On the competition numbers of diamond-free graphs
• A generalization of Opsut's lower bounds for the competition number of a graph
• 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
• A generalization of Opsut's result on the competition numbers of line graphs
• The competition numbers of Johnson graphs with diameter four
• Partial characterizations of 1-perfectly orientable graphs
• Graphs having many holes but with small competition numbers
• The competition numbers of ternary Hamming graphs
• Competition graphs of degree bounded digraphs
• Competition numbers of complete \(r\)-partite graphs
• On Opsut's conjecture for hypercompetition numbers of hypergraphs
• Applications of edge coverings by cliques
• A mathematical approach on representation of competitions: competition cluster hypergraphs
• Edge-clique covers of the tensor product
• Characterizations of competition multigraphs
• An upper bound for the competition numbers of graphs
• Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
• The competition number of a graph whose holes do not overlap much

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4750663)