Can I read The Competition Number of a Graph in Which Any Two Holes Share at Most One Edge on EtoBox?

The Competition Number of a Graph in Which Any Two Holes Share at Most One Edge by Lee, Jung Yeun; Kim, Suh-Ryung; Sano, Yoshio is a scholarly article available to read on EtoBox.

What is The Competition Number of a Graph in Which Any Two Holes Share at Most One Edge about?

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number. A hole of a graph is a cycle of length at least 4 as an induced subgraph. It holds that the competition number of a graph cannot exceed one plus the number of its holes if G satisfies a certain condition. In this paper, we show that the competition number of a graph with exactly h holes any two of which share at most one edge is at most h+1, which generalizes the existing results on this subject.

Author

Lee, Jung Yeun; Kim, Suh-Ryung; Sano, Yoshio

Published

2011

Language

EN