×

Dimension-2 poset competition numbers and dimension-2 poset double competition numbers. (English) Zbl 1225.05188

Summary: Let \(D=(V(D),A(D))\) be a digraph. The competition graph of \(D\), is the graph with vertex set \(V(D)\) and edge set \(\{uv \in \binom {v(D)}{2} : \exists w \in V(D), \overrightarrow {uw}, \overrightarrow {vw} \in A(D) \}\). The double competition graph of \(D\), is the graph with vertex set \(V(D)\) and edge set \(\{uv \in \binom {v(D)}{2} : \exists w \in V(D), \overrightarrow {uw_1}, \overrightarrow {vw_1}, \overrightarrow {w_2u}, \overrightarrow {w_2v} \in A(D) \}\). A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane \(\mathbb R^2\) and there is an arc going from a vertex \((x_{1},y_{1})\) to a vertex \((x_{2},y_{2})\) if and only if \(x_{1}>x_{2}\) and \(y_{1}>y_{2}\).
We show that a graph is the competition graph of a poset of dimension at most two if and only if it is an interval graph, at least half of whose maximal cliques are isolated vertices. This answers an open question on the doubly partial order competition number posed by Cho and Kim. We prove that the double competition graph of a poset of dimension at most two must be a trapezoid graph, generalizing a result of Kim, Kim, and Rho. Some connections are also established between the minimum numbers of isolated vertices required to be added to change a given graph into the competition graph, the double competition graph, of a poset and the minimum sizes of certain intersection representations of that graph.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnabei, M.; Bonetti, F.; Pirastu, R., A characteristic property of labellings and linear extensions of posets of dimension 2, Adv. in Appl. Math., 21, 685-690 (1998) · Zbl 0922.06003
[2] Bazzaro, F.; Gavoille, C., Localized and compact data-structure for comparability graphs, Discrete Math., 309, 3465-3484 (2009) · Zbl 1221.05105
[3] Benzer, S., On the topology of the genetic fine structure, Proc. Natl. Acad. Sci. USA, 45, 1607-1620 (1959)
[4] Brandstädt, A.; Le, V. B.; Spinrad, J. P., (Graph Classes: A Survey. Graph Classes: A Survey, SIAM Monographs on Discrete Mathmatics and Application, vol. 3 (1999), SIAM: SIAM Philadelphia) · Zbl 0919.05001
[5] Cattin, M.-F.; Bersier, L.-F.; Banas¨ek-Richter, C.; Baltensperger, R.; Gabriel, J.-P., Phylogenetic constraints and adaptation explain food-web structure, Nature, 427, 835-839 (2004)
[6] Chandran, L. S.; Sivadasan, N., Boxicity and treewidth, J. Combin. Theory Ser. B, 97, 733-744 (2007) · Zbl 1121.05091
[7] Cheston, G. A.; Jap, T. S., A survey of the algorithmic properties of simplicial, upper bound and middle graphs, J. Graph Algorithms Appl., 10, 159-190 (2006) · Zbl 1161.68648
[8] Cho, H. H.; Kim, S.-R., A class of acyclic digraphs with interval competition graphs, Discrete Appl. Math., 148, 171-180 (2005) · Zbl 1071.05040
[9] Cogis, O., On the Ferrers dimension of a digraph, Discrete Math., 38, 47-52 (1982) · Zbl 0472.06007
[10] Cohen, J. E., Interval graphs and food webs: A finding and a problem, (Document 17986-PR (1968), Rand Corporation: Rand Corporation Santa Monica, CA)
[11] Cohen, J. E., Food Webs and Niche Spaces (1978), Princeton University Press: Princeton University Press Princeton, NJ
[12] Cohen, J. E., Recent progress and problems in food web theory, (DeAngelis, D. L.; Post, W. M.; Sugihara, G., Current Trends in Food Web Theory. Current Trends in Food Web Theory, ORNL, vol. 5983 (1983), Oak Ridge National Laboratory: Oak Ridge National Laboratory Oak Ridge, TN), 17-24
[13] Cohen, J. E.; Komlós, J.; Mueller, T., The probability of an interval graph, and why it matters, Proc. Sympos. Pure Math., 34, 97-115 (1979) · Zbl 0403.05053
[14] Corneil, D. G.; Kamula, P. A., Extensions of permutation and interval graphs, Congr. Numer., 58, 267-275 (1987) · Zbl 0652.05055
[15] Cozzens, M. B.; Roberts, F. S., Computing the boxicity of a graph by covering its complement by cointerval graphs, Discrete Appl. Math., 6, 217-228 (1983) · Zbl 0524.05059
[16] Dagan, I.; Golumbic, M. C.; Pinter, R. Y., Trapezoid graphs and their coloring, Discrete Appl. Math., 21, 35-46 (1988) · Zbl 0658.05067
[17] Dutton, R. D.; Brigham, R. C., A characterization of competition graphs, Discrete Appl. Math., 6, 315-317 (1983) · Zbl 0521.05057
[18] Era, H.; Ogawa, K.; Tsuchiya, M., On upper bound graphs with respect to operations on graphs, Theoret. Comput. Sci., 235, 219-223 (2000) · Zbl 0938.68060
[19] Era, H.; Ogawa, K.; Tsuchiya, M., On transformations of posets which have the same bound graph, Discrete Math., 235, 215-220 (2001) · Zbl 0977.05113
[20] Era, H.; Ogawa, K.; Tsuchiya, M., On upper bound graphs with respect to unary operations on graphs, Ann. Comb., 6, 1-6 (2002) · Zbl 1009.05117
[21] Erdős, P.; Goodman, A. W.; Pósa, L., The representation of a graph by set intersections, Canad. J. Math., 18, 106-112 (1966) · Zbl 0137.43202
[22] Felsner, S., Tolerance graphs and orders, J. Graph Theory, 28, 129-140 (1998) · Zbl 0921.05053
[23] Fishburn, P. C., Interval Order and Interval Graphs: A Study of Partially Ordered Sets (1985), John Wiley: John Wiley New York · Zbl 0551.06001
[24] Fishburn, P. C., Intransitive indifference with unequal indifference intervals, J. Math. Psych., 7, 144-149 (1970) · Zbl 0191.31501
[25] Fishburn, P. C.; Trotter, W. T., Geometric containment orders: A survey, Order, 15, 167-182 (1999) · Zbl 0935.06001
[26] Füredi, Z., On the double competition number, Discrete Appl. Math., 82, 251-255 (1998) · Zbl 0903.05031
[27] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003
[28] Golumbic, M. C.; Trenk, A. N., (Tolerance Graphs. Tolerance Graphs, Cambridge Studies in Advanced Mathematics, vol. 89 (2004), Cambridge: Cambridge United Kingdom) · Zbl 1091.05001
[29] Guichard, D. R., Competition graphs of Hamiltonian digraphs, SIAM J. Discrete Math., 11, 128-134 (1998) · Zbl 0910.05030
[30] Hajös, G., Über eine Art von Graphen, Math. Nachr., 11 (1957), Problem 65
[31] Jones, K. F.; Lundgren, J. R.; Roberts, F. S.; Seager, S., Some remarks on the double competition number of a graph, Congr. Numer., 60, 17-24 (1987)
[32] Jordán, F.; Molnár, I., Reliable flows and preferred patterns in food webs, Evol. Ecol. Res., 1, 591-609 (1999)
[33] Kim, S.-J.; Kim, S.-R.; Rho, Y., On CCE graphs of doubly partial orders, Discrete Appl. Math., 155, 971-978 (2007) · Zbl 1118.05041
[34] Kim, S.-R., The competition number and its variants, (Quo Vadis, Graph Theory?. Quo Vadis, Graph Theory?, Ann. Discrete Math., vol. 55 (1993), North-Holland: North-Holland Amsterdam), 313-326 · Zbl 0789.05041
[35] Kong, J.; Wu, Y., Recognizing edge clique graphs among interval graphs and probe interval graphs, Appl. Math. Lett., 20, 1000-1004 (2007) · Zbl 1152.05364
[36] Kong, J.; Wu, Y., On economical set representations of graphs, Discrete Math. Theor. Comput. Sci., 11, 71-96 (2009) · Zbl 1196.05056
[37] Kratochvil, J., A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Appl. Math., 52, 233-252 (1994) · Zbl 0810.68083
[38] Lu, J.; Wu, Y., Two minimal forbidden subgraphs for double competition graphs of posets of dimension at most two, Appl. Math. Lett., 22, 841-845 (2009) · Zbl 1185.05120
[39] J. Lu, Y. Wu, Double competition graphs of posets of dimension at most two and tolerance graphs (submitted for publication) Available at: http://math.sjtu.edu.cn/teacher/wuyk/dcp-09-03-10.pdf; J. Lu, Y. Wu, Double competition graphs of posets of dimension at most two and tolerance graphs (submitted for publication) Available at: http://math.sjtu.edu.cn/teacher/wuyk/dcp-09-03-10.pdf
[40] Lundgren, J. R., Food webs, competition graphs, competition-common enemy graphs, and niche graphs, (Roberts, F. S., Applications of Combinatorics and Graph Theory in the Biological and Social Sciences. Applications of Combinatorics and Graph Theory in the Biological and Social Sciences, IMA Volumes in Mathematics and its Applications, vol. 17 (1989), Springer: Springer New York), 221-243 · Zbl 0701.92023
[41] Lundgren, J. R.; Maybee, J. S., A characterization of graphs of competition number \(m\), Discrete Appl. Math., 6, 319-322 (1983) · Zbl 0521.05058
[42] McConnell, R. M.; Spinrad, J. P., Linear-time transitive orientation, (8th Symposium on Discrete Algorithms (1997), ACM-SIAM), 19-25 · Zbl 1321.05272
[43] McGuigan, R. A., Food webs, (Michaels, J. G.; Rosen, K. H., Applications of Discrete Mathematics (2007), McGraw-Hill), 225-240, (Chapter 13)
[44] McKee, T. A., Upper bound multigraphs for posets, Order, 6, 265-275 (1989) · Zbl 0723.05106
[45] McKee, T. A.; McMorris, F. R., (Topics in Intersection Graph Theory. Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Application, vol. 2 (1999), SIAM: SIAM Philadelphia) · Zbl 0945.05003
[46] McMorris, F. R.; Myers, G. T., Some uniqueness results for upper bound graphs, Discrete Math., 44, 321-323 (1983) · Zbl 0518.05052
[47] McMorris, F. R.; Zaslavsky, T., Bound graphs of a partially ordered set, J. Comb. Inf. Syst. Sci., 7, 134-138 (1982) · Zbl 0525.05060
[48] 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
[49] Opsut, R. J.; Roberts, F. S., On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems, (Chartrand, G.; Alavi, Y.; Goldsmith, D. L.; Lesniak-Foster, L.; Lick, D. R., The Theory and Applications of Graphs (1981), Wiley: Wiley New York), 479-492 · Zbl 0471.05032
[50] Pimm, S. L.; Lawton, J. H.; Cohen, J. E., Food web patterns and their consequences, Nature, 350, 669-674 (1991)
[51] Raychaudhuri, A.; Roberts, F. S., Generalized competition graphs and their applications, Methods Oper. Res., 49, 295-311 (1985) · Zbl 0572.05050
[52] Roberts, F. S., On the boxicity and cubicity of a graph, (Tutte, W. T., Recent Progress in Combinatorics (1969), Academic Press: Academic Press New York), 301-310 · Zbl 0193.24301
[53] F.S. Roberts, Food webs, competition graphs, and the boxicity of ecological phase space, in: Y. Alavi, D. Lick (Eds.), Theory and Applications of Graphs, New York, 1978, pp. 477-490; F.S. Roberts, Food webs, competition graphs, and the boxicity of ecological phase space, in: Y. Alavi, D. Lick (Eds.), Theory and Applications of Graphs, New York, 1978, pp. 477-490
[54] Roberts, F. S., Applications of edge coverings by cliques, Discrete Appl. Math., 10, 93-109 (1985) · Zbl 0558.05046
[55] Scheinerman, E. R., Geometry, (Beineke, L. W.; Wilson, R. J., Graph Connections (1997), Clarendon Press), 141-154 · Zbl 0878.05073
[56] Scott, D. D., Posets with interval upper bound graphs, Order, 3, 269-281 (1986) · Zbl 0647.06002
[57] Scott, D. D., The competition-common enemy graph of a digraph, Discrete Appl. Math., 17, 269-280 (1987) · Zbl 0609.05038
[58] Seager, S. M., The double competition number of some triangle-free graphs, Discrete Appl. Math., 28, 265-269 (1990) · Zbl 0723.05063
[59] Trotter, W. T., Combinatorics and Partially Ordered Sets: Dimension Theory (1992), Johns Hopkins Univ. Press · Zbl 0764.05001
[60] West, D. B., Introduction to Graph Theory (2004), China Machine Press
[61] Wiener, N., A contribution to the theory of relative position, Proc. Cambridge Philos. Soc., 27, 441-449 (1914) · JFM 45.1150.10
[62] Winemiller, K. O.; Pianka, E. R.; Vitt, L. J.; Joern, A., Food web laws or niche theory? Six independent empirical tests, Amer. Soc. Natur., 158, 193-199 (2001)
[63] Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. Algebr. Discrete Methods, 3, 351-358 (1982) · Zbl 0516.06001
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.