The phylogeny graphs of doubly partial orders

DOI10.7151/DMGT.1701MaRDI QIDQ5495048zbMATH OpenOpenAlexFDO

Authors Boram Park, Yoshio Sano

Publication date 30 July 2014

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1103.4540

zbMATH Keywords

competition graphdoubly partial orderinterval graphphylogeny graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Structural characterization of families of graphs (05C75) Problems related to evolution (92D15)

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)):=xymid{N}_D^{+}(x)cap{N}_D^{+}(y)eqemptysetcupxymid(x,y)inA(D)$, where $N_D^{+}(x):=vinV(D)mid(x,v)inA(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 $ildeG$ such that $ildeG$ contains the graph $G$ as an induced subgraph and that $ildeG$ is the phylogeny graph of a doubly partial order.

Recommendations

• The niche graphs of doubly partial orders
• The m-step competition graphs of doubly partial orders
• scientific article; zbMATH DE number 1113981
• The competition hypergraphs of doubly partial orders
• Phylogeny numbers

Cited in

(8)

• The partial order competition dimensions of bipartite graphs
• A graph with the partial order competition dimension greater than five
• On the partial order competition dimensions of chordal graphs
• On the phylogeny graphs of degree-bounded digraphs
• The competition hypergraphs of doubly partial orders
• On the competition graphs of \(d\)-partial orders
• The niche graphs of doubly partial orders
• On CCE graphs of doubly partial orders

This page was built for publication: The phylogeny graphs of doubly partial orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495048)