Wyniki wyszukiwania

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.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

The competition numbers of Johnson graphs

81%

Kim S.-R., Park B., Sano Y.

Discussiones Mathematicae Graph Theory

2010

tom 30

nr 3

449-459

The competition graph of a digraph D is a graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and to characterize all graphs with given competition number k has been one of the important research problems in the study of competition graphs. The Johnson graph J(n,d) has the vertex set ${v_X | X ∈ \binom{[n]}{d}$, where $\binom{[n]}{d}$ denotes the set of all d-subsets of an n-set [n] = {1,..., n}, and two vertices $v_{X₁}$ and $v_{X₂}$ are adjacent if and only if |X₁ ∩ X₂| = d - 1. In this paper, we study the edge clique number and the competition number of J(n,d). Especially we give the exact competition numbers of J(n,2) and J(n,3).

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Park B.

2 Sano Y.

1 Kim S.-R.

1 2013

1 2010

Wyniki wyszukiwania

The Phylogeny Graphs of Doubly Partial Orders

The competition numbers of Johnson graphs