Graphs having many holes but with small competition numbers. (English) Zbl 1222.05086
Summary: The competition number \(k(G)\) of a graph \(G\) is the smallest number \(k\) such that \(G\) together with \(k\) isolated vertices added is the competition graph of an acyclic digraph. A chordless cycle of length at least 4 of a graph is called a hole of the graph. The number of holes of a graph is closely related to its competition number as the competition number of a graph which does not contain a hole is at most one and the competition number of a complete bipartite graph \(K_{\lfloor \frac n2\rfloor, \lceil\frac n2\rceil}\) which has so many holes that no more holes can be added is the largest among those of graphs with \(n\) vertices.
In this paper, we show that even if a connected graph \(G\) has many holes, the competition number of \(G\) can be as small as 2 under some assumption. In addition, we show that, for a connected graph \(G\) with exactly \(h\) holes and at most one non-edge maximal clique, if all the holes of \(G\) are pairwise edge-disjoint and the clique number \(\omega =\omega (G)\) of \(G\) satisfies \(2\leq \omega \leq h+1\), then the competition number of \(G\) is at most \(h - \omega +3\).
In this paper, we show that even if a connected graph \(G\) has many holes, the competition number of \(G\) can be as small as 2 under some assumption. In addition, we show that, for a connected graph \(G\) with exactly \(h\) holes and at most one non-edge maximal clique, if all the holes of \(G\) are pairwise edge-disjoint and the clique number \(\omega =\omega (G)\) of \(G\) satisfies \(2\leq \omega \leq h+1\), then the competition number of \(G\) is at most \(h - \omega +3\).
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North Holland: North Holland New York · Zbl 1134.05001 |
| [2] | Cohen, J. E., Interval Graphs and Food Webs: a Finding and a Problem (1968), Document 17696-PR, RAND Corporation: Document 17696-PR, RAND Corporation Santa Monica, CA |
| [3] | Raychaudhuri, A.; Roberts, F. S., Generalized competition graphs and their applications, (Brücker, P.; Pauly, R., Methods of Operations Research, 49 (1985), Anton Hain, Königstein: Anton Hain, Königstein West Germany), 295-311 · Zbl 0572.05050 |
| [4] | Roberts, F. S., Competition graphs and phylogeny graphs, (Lovasz, L., Graph Theory and Combinatorial Biology Bolyai Mathematical Studies, vol. 7 (1999), J. Bolyai Mathematical Society: J. Bolyai Mathematical Society Budapest), 333-362 · Zbl 0924.05032 |
| [5] | Greenberg, H. J.; Lundgren, J. R.; Maybee, J. S., Graph-theoretic foundations fo computer-assisted analysis, (Greenberg, H. J.; Maybee, J. S., Computer-Assisted Analysis and Model Simplification (1981), Academic Press: Academic Press New York), 481-495 |
| [6] | Roberts, F. S., Food webs, competition graphs, and the boxicity of ecological phase space, (Alavi, Y.; Lick, D., Theory and Applications of Graphs (1978), Western Mich. Univ: Western Mich. Univ Kalamazoo, Mich), 477-490, Proc. Internat. Conf. 1976 · Zbl 0389.90036 |
| [7] | Opsut, R. J., On the computation of the competition number of a graph, SIAM J. Algebr. Discrete Methods, 3, 420-428 (1982) · Zbl 0512.05032 |
| [8] | Harary, F.; Kim, S.-R.; Roberts, F. S., Extremal competition numbers as a generalization of Turan’s theorem, J. Ramanujan Math. Soc., 5, 33-43 (1990) · Zbl 0721.05034 |
| [9] | Cho, H. H.; Kim, S.-R., The competition number of a graph having exactly one hole, Discrete Math., 303, 32-41 (2005) · Zbl 1079.05041 |
| [10] | Kim, S.-R., Graphs with one hole and competition number one, J. Korean Math. Soc., 42, 1251-1264 (2005) · Zbl 1082.05046 |
| [11] | Kim, S.-R.; Lee, J. Y.; Sano, Y., The competition number of a graph whose holes do not overlap much, Discrete Appl. Math., 158, 1456-1460 (2010) · Zbl 1209.05110 |
| [12] | Lee, J. Y.; Kim, S.-R.; Kim, S.-J.; Sano, Y., The competition number of a graph with exactly two holes, Ars Combin., 95, 45-54 (2010) · Zbl 1249.05167 |
| [13] | Li, B.-J.; Chang, G. J., The competition number of a graph with exactly \(h\) holes, all of which are independent, Discrete Appl. Math., 157, 1337-1341 (2009) · Zbl 1204.05050 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
