Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: doubly partial order

Sortuj według:

Ogranicz wyniki do:

The Phylogeny Graphs of Doubly Partial Orders

100%

Park B., Sano Y.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 4

657-664

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Park B.

1 Sano Y.

1 2013

Wyniki wyszukiwania

The Phylogeny Graphs of Doubly Partial Orders