×

zbMATH — the first resource for mathematics

\(p\)-competition graphs. (English) Zbl 0824.05027
The \(p\)-competition graph of a digraph \(D= (V, A)\) is the graph with vertex set \(V\) and an edge between \(x\) and \(y\) whenever there exist distinct vertices \(v_ 1, v_ 2,\dots, v_ p\) and arcs \((x, v_ i)\), \((y,v_ i)\) in \(D\) for each \(i\leq p\). In case \(p= 1\) the concept coincides with the competition graph which has received a great deal of attention in the literature since being introduced by J. E. Cohen in 1968, see, e.g., R. D. Dutton and R. C. Brigham [A characterization of competition graphs, Discrete Appl. Math. 6, 315-317 (1983; Zbl 0521.05057)]. In the present paper, the authors study properties of \(p\)-competition graphs, obtaining, where possible, analogues of results about ordinary competition graphs.

MSC:
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anderson, C.A.; Jones, K.F.; Lundgren, J.R.; McKee, T.A., Competition multigraphs and the multicompetition number, Ars combin, 29B, 185-192, (1990) · Zbl 0745.05053
[2] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), American Elsevier New York · Zbl 1134.05001
[3] Bowser, S.; Cable, C.A., Some recent results on niche graphs, Discrete appl. math., 30, 101-108, (1991) · Zbl 0713.05032
[4] Brigham, R.C.; Dutton, R.D.; McMorris, F.R.; Mize, J.B., On p-edge clique covers of graphs, (), 149-157 · Zbl 0801.05056
[5] Cable, C.; Jones, K.F.; Lundgren, J.R.; Seager, S., Niche graphs, Discrete appl. math., 23, 231-241, (1989) · Zbl 0677.05039
[6] M. S. Chung and D. B. West, The p-intersection number of a complete bipartite graph and orthogonal double coverings of a clique, submitted for publication. · Zbl 0813.05055
[7] Cohen, J.E., Interval graphs and food webs: A finding and a problem, ()
[8] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[9] Dutton, R.D.; Brigham, R.C., A characterization of competition graphs, Discrete appl. math., 6, 315-317, (1983) · Zbl 0521.05057
[10] Fishburn, P.C.; Gehrlein, W.V., Niche numbers, J. graph theory, 16, 131-139, (1992) · Zbl 0758.05092
[11] Füredi, Z., Competition graphs and clique dimensions, Random structures algorithms, 1, 183-189, (1990) · Zbl 0764.05091
[12] Hefner, K.A.S.; Jones, K.F.; Kim, S.; Lundgren, J.R.; Roberts, F.S., (i,j) competition graphs, Discrete appl. math., 32, 241-262, (1991) · Zbl 0746.05028
[13] Isaak, G.; Kim, S.; McKee, T.A.; McMorris, F.R.; Roberts, F.S., 2-competition graphs, SIAM J. discrete math., 5, 524-538, (1992) · Zbl 0767.05087
[14] Jacobson, M.S., On the p-edge clique cover numbers of complete bipartite graphs, SIAM J. discrete math., 5, 539-544, (1992) · Zbl 0773.05067
[15] Jacobson, M.S.; McMorris, F.R.; Mulder, H.M., An introduction to tolerance intersection graphs, (), 705-723 · Zbl 0840.05079
[16] Jacobson, M.S.; McMorris, F.R.; Scheinerman, E.R., General results on tolerance intersection graphs, J. graph theory, 15, 573-577, (1991) · Zbl 0741.05070
[17] M. S. Jacobson, A. E. Kézdy, and D. B. West, The 2-intersection number of paths and bounded-degree trees, submitted for publication. · Zbl 0829.05037
[18] Jones, K.R.; Lundgren, J.R.; Roberts, F.S.; Seager, S., Some remarks on the double competition number of a graph, (), 17-24
[19] Kim, S., Competition graphs and scientific laws for food webs and other systems, ()
[20] Kim, S.; McKee, T.A.; McMorris, F.R.; Roberts, F.S., p-competition graphs, ()
[21] Kim, S.; McKee, T.A.; McMorris, F.R.; Roberts, F.S., p-competition numbers, Discrete appl. math., 46, 87-92, (1993) · Zbl 0785.05044
[22] Kim, S.; Roberts, F.S.; Seager, S., On 101-clear (0, 1) matrices and the double competition number of bipartite graphs, J. combin. inform. system sci., 17, 302-315, (1992) · Zbl 1230.05069
[23] Lundgren, J.R., Food webs, competition graphs, competition-common enemy graphs, and niche graphs, (), 221-243 · Zbl 0701.92023
[24] Lundgren, J.R.; Maybee, J.S., A characterization of graphs of competition number m, Discrete appl. math., 6, 319-322, (1983) · Zbl 0521.05058
[25] Lundgren, J.R.; Maybee, J.S., A characterization of upper bound graphs, (), 189-193
[26] Lundgren, J.R.; Maybee, J.S., Food webs with interval competition graphs, (), 245-256
[27] Major, G.; McMorris, F.R., P-edge clique coverings of graphs, (), 143-145 · Zbl 0862.05088
[28] McKee, T.A., Foundations of intersection graph theory, Utilitas math., 40, 77-86, (1991) · Zbl 0752.05042
[29] McMorris, F.R.; Myers, G.T., Some uniqueness results for upper bound graphs, Discrete math., 44, 321-323, (1983) · Zbl 0518.05052
[30] McMorris, F.R.; Zaslavsky, T., Bound graphs of a partially ordered set, J. combin. inform. system sci., 7, 134-138, (1982) · Zbl 0525.05060
[31] Raychaudhuri, A.; Roberts, F.S., Generalized competition graphs and their applications, (), 295-311 · Zbl 0572.05050
[32] Roberts, F.S., Food webs, competition graphs, and the boxicity of ecological phase space, (), 477-490
[33] Roberts, F.S., Applied combinatorics, (1984), Prentice-Hall Englewood Cliffs, N. J · Zbl 0547.05001
[34] Roberts, F.S., Applications of edge coverings by cliques, Discrete appl. math., 10, 93-109, (1985) · Zbl 0558.05046
[35] Roberts, F.S.; Steif, J.E., A characterization of competition graphs of arbitrary digraphs, Discrete appl. math., 6, 323-326, (1983) · Zbl 0521.05059
[36] Scott, D., The competition-common enemy graph of a digraph, Discrete appl. math., 17, 269-280, (1987) · Zbl 0609.05038
[37] Seager, S.M., The double competition number of some triangle-free graphs, Discrete appl. math., 28, 265-269, (1990) · Zbl 0723.05063
[38] Sugihara, G., Graph theory, homology, and food webs, (), 83-101
[39] Wang, C., Competition graphs, threshold graphs, and threshold Boolean functions, ()
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.