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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.