The Phylogeny Graphs of Doubly Partial Orders

Boram Park; Yoshio Sano

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 4, page 657-664
  • ISSN: 2083-5892

Abstract

top
The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V (P(D)) := V (D) and E(P(D)) := {xy | N+D (x) ∩ N+D(y) ¹ ⊘ } ⋃ {xy | (x,y) ∈ A(D)}, where N+D(x):= {v ∈ V(D) | (x,v) ∈ A (D)}. In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph G̃, there exists an interval graph G such that G̃ contains the graph G as an induced subgraph and that G̃ is the phylogeny graph of a doubly partial order.

How to cite

top

Boram Park, and Yoshio Sano. "The Phylogeny Graphs of Doubly Partial Orders." Discussiones Mathematicae Graph Theory 33.4 (2013): 657-664. <http://eudml.org/doc/267778>.

@article{BoramPark2013,
abstract = {The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V (P(D)) := V (D) and E(P(D)) := \{xy | N+D (x) ∩ N+D(y) ¹ ⊘ \} ⋃ \{xy | (x,y) ∈ A(D)\}, where N+D(x):= \{v ∈ V(D) | (x,v) ∈ A (D)\}. In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph G̃, there exists an interval graph G such that G̃ contains the graph G as an induced subgraph and that G̃ is the phylogeny graph of a doubly partial order.},
author = {Boram Park, Yoshio Sano},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {competition graph; phylogeny graph; doubly partial order; interval graph},
language = {eng},
number = {4},
pages = {657-664},
title = {The Phylogeny Graphs of Doubly Partial Orders},
url = {http://eudml.org/doc/267778},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Boram Park
AU - Yoshio Sano
TI - The Phylogeny Graphs of Doubly Partial Orders
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 4
SP - 657
EP - 664
AB - The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph P(D) of a digraph D is the (simple undirected) graph defined by V (P(D)) := V (D) and E(P(D)) := {xy | N+D (x) ∩ N+D(y) ¹ ⊘ } ⋃ {xy | (x,y) ∈ A(D)}, where N+D(x):= {v ∈ V(D) | (x,v) ∈ A (D)}. In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph G̃, there exists an interval graph G such that G̃ contains the graph G as an induced subgraph and that G̃ is the phylogeny graph of a doubly partial order.
LA - eng
KW - competition graph; phylogeny graph; doubly partial order; interval graph
UR - http://eudml.org/doc/267778
ER -

References

top
  1. [1] C. Cable, K.F. Jones, J.R. Lundgren and S. Seager, Niche graphs, Discrete Appl. Math. 23 (1989) 231-241. doi:10.1016/0166-218X(89)90015-2[Crossref] Zbl0677.05039
  2. [2] H.H. Cho and S.-R. Kim, A class of acyclic digraphs with interval competition graphs, Discrete Appl. Math. 148 (2005) 171-180. doi:10.1016/j.dam.2005.02.005[Crossref] Zbl1071.05040
  3. [3] J.E. Cohen, Interval graphs and food webs. A finding and a problem, RAND Corporation Document 17696-PR (Santa Monica, California, 1968). 
  4. [4] D.C. Fisher, J.R. Lundgren, S.K. Merz and K.B. Reid, The domination and competition graphs of a tournament , J. Graph Theory 29 (1998) 103-110. doi:10.1002/(SICI)1097-0118(199810)29:2h103::AID-JGT6i3.0.CO;2-V[Crossref] Zbl0919.05024
  5. [5] K.F. Fraughnaugh, J.R. Lundgren, J.S. Maybee, S.K. Merz and N.J. Pullman, Competition graphs of strongly connected and hamiltonian digraphs, SIAM J. Discrete Math. 8 (1995) 179-185. doi:10.1137/S0895480191197234[Crossref] Zbl0830.05035
  6. [6] S.-R. Kim The competition number and its variants, in: Quo Vadis Graph Theory?, J. Gimbel, J.W. Kennedy, and L.V. Quintas (Eds.), Ann. Discrete Math. 55 (1993) 313-325. 
  7. [7] S.-J. Kim, S.-R. Kim and Y. Rho, On CCE graphs of doubly partial orders, Discrete Appl. Math. 155 (2007) 971-978. doi:10.1016/j.dam.2006.09.013[WoS][Crossref] Zbl1118.05041
  8. [8] S.-R. Kim, J.Y. Lee, B. Park, W.J. Park and Y. Sano, The niche graphs of doubly partial orders, Congr. Numer. 195 (2009) 19-32. Zbl1218.05061
  9. [9] S.-R. Kim, J.Y. Lee, B. Park and Y. Sano, The competition hypergraphs of doubly partial orders, Discrete Appl. Math. doi:10.1016/j.dam.2012.05.024[Crossref] Zbl1288.05187
  10. [10] S.-R. Kim and F.S. Roberts, Competition graphs of semiorders and the conditions C(p) and C(p), Ars Combin. 63 (2002) 161-173. 
  11. [11] J.Y. Lee and S.-R. Kim, Competition graphs of acyclic digraphs satisfying condition C(p), Ars Combin. 93 (2009) 321-332. Zbl1224.05212
  12. [12] J.R. Lundgren, Food webs, competition graphs, competition-common enemy graphs, and niche graphs, in: Applications of Combinatorics and Graph Theory in the Biological and Social Sciences, F.S. Roberts (Ed.), IMA Volumes in Mathematics and its Applications, 17 ( Springer-Verlag, New York, 1989) 221-243. 
  13. [13] J.R. Lundgren, J.S. Maybee and C.W. Rasmussen, Interval competition graphs of symmetric digraphs, Discrete Math. 119 (1993) 113-122. doi:10.1016/0012-365X(93)90121-9[Crossref] 
  14. [14] B. Park, J.Y. Lee and S.-R. Kim, The m-step competition graphs of doubly partial orders, Appl. Math. Lett. 24 (2011) 811-816. doi:10.1016/j.aml.2010.12.009[WoS][Crossref] Zbl1226.05127
  15. [15] B. Park and Y. Sano, On the hypercompetition numbers of hypergraphs, Ars Combin. 100 (2011) 151-159. Zbl1265.05449
  16. [16] F.S. Roberts, Competition graphs and phylogeny graphs, in: Graph Theory and Combinatorial Biology, L. Lovasz (Ed.), Bolyai Mathematical Studies, 7, (János Bolyai Mathematical Society, Budapest, 1999) 333-362. Zbl0924.05032
  17. [17] F.S. Roberts and L. Sheng, Phylogeny graphs of arbitrary digraphs, Mathematical Hierarchies and Biology (Piscataway, NJ, 1996) DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 37 Amer. Math. Soc. (1997) 233-237. Zbl0887.05048
  18. [18] F.S. Roberts and L. Sheng, Phylogeny numbers, Discrete Appl. Math. 87 (1998) 213-228. doi:10.1016/S0166-218X(98)00058-4[Crossref] Zbl0907.05024
  19. [19] F.S. Roberts and L. Sheng, Phylogeny numbers for graphs with two triangles, Discrete Appl. Math. 103 (2000) 191-207. doi:10.1016/S0166-218X(99)00209-7[Crossref] Zbl0953.05027
  20. [20] Y. Sano, Characterizations of competition multigraphs, Discrete Appl. Math. 157 (2009) 2978-2982. doi:10.1016/j.dam.2009.04.010[Crossref][WoS] 
  21. [21] Y. Sano, The competition-common enemy graphs of digraphs satisfying Conditions C(p) and C′(p), Congr. Numer. 202 (2010) 187-194. Zbl1231.05114
  22. [22] D.D. Scott, The competition-common enemy graph of a digraph, Discrete Appl. Math. 17 (1987) 269-280. doi:10.1016/0166-218X(87)90030-8[Crossref] 
  23. [23] M. Sonntag and H.-M. Teichert, Competition hypergraphs, Discrete Appl. Math. 143 (2004) 324-329. doi:10.1016/j.dam.2004.02.010[Crossref] 
  24. [24] Y. Wu and J. Lu, Dimension-2 poset competition numbers and dimension-2 poset double competition numbers, Discrete Appl. Math. 158 (2010) 706-717. doi:10.1016/j.dam.2009.12.001 [Crossref] Zbl1225.05188

NotesEmbed ?

top

You must be logged in to post comments.