Discussiones Mathematicae Graph Theory 33(4) (2013)
657-664

doi: 10.7151/dmgt.1701

Boram Park
National Institute for Mathematical Sciences | Yoshio Sano
Division of Information Engineering |

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.

**Keywords:** competition graph, phylogeny graph, doubly partial order, interval graph

**2010 Mathematics Subject Classification:** 05C20, 05C75.

[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. |

[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. |

[3] | J.E. Cohen, Interval graphs and food webs. A finding and a problem, RAND Corporation Document 17696-PR (Santa Monica, California, 1968). |

[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:2<103::AID-JGT6>3.0.CO;2-V . |

[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. |

[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] | 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. |

[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. |

[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. |

[10] | S.-R. Kim and F.S. Roberts, Competition graphs of semiorders and the conditions , Ars Combin. C(p) and C^{*}(p) 63 (2002) 161--173. |

[11] | J.Y. Lee and S.-R. Kim, Competition graphs of acyclic digraphs satisfying condition , Ars Combin. C^{*}(p) 93 (2009) 321--332. |

[12] | J.R. Lundgren, Food webs, competition graphs, competition-c. |

[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. |

[14] | B. Park, J.Y. Lee and S.-R. Kim, The , Appl. Math. Lett. m-step competition graphs of doubly partial orders 24 (2011) 811--816, doi: 10.1016/j.aml.2010.12.009. |

[15] | B. Park and Y. Sano, On the hypercompetition numbers of hypergraphs, Ars Combin. 100 (2011) 151--159. |

[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. |

[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. |

[18] | F.S. Roberts and L. Sheng, Phylogeny numbers, Discrete Appl. Math. 87 (1998) 213--228, doi: 10.1016/S0166-218X(98)00058-4. |

[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. |

[20] | Y. Sano, Characterizations of competition multigraphs, Discrete Appl. Math. 157 (2009) 2978--2982, doi: 10.1016/j.dam.2009.04.010. |

[21] | Y. Sano, The competition-common enemy graphs of digraphs satisfying Conditions , Congr. Numer. C(p) and C'(p) 202 (2010) 187--194. |

[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. |

[23] | M. Sonntag and H.-M. Teichert, Competition hypergraphs, Discrete Appl. Math. 143 (2004) 324--329, doi: 10.1016/j.dam.2004.02.010. |

[24] | Y. Wu and J. Lu, Dimension-, Discrete Appl. Math. 2 poset competition numbers and dimension-2 poset double competition numbers 158 (2010) 706--717, doi: 10.1016/j.dam.2009.12.001. |

Received 2 November 2011

Revised 26 July 2012

Accepted 30 July 2012