Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: jump distance graph

Sortuj według:

Ogranicz wyniki do:

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

Rotation and jump distances between graphs

100%

Chartrand G., Gavlas H., Hevia H., Johnson M.

Discussiones Mathematicae Graph Theory

1997

tom 17

nr 2

285-300

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least 5) and same size, G can be j-transformed into H. For every two graphs G and H of the same order and same size, the jump distance $d_j(G,H)$ between G and H is defined as the minimum number of edge jumps required to j-transform G into H. The rotation distance $d_r(G,H)$ between two graphs G and H of the same order and same size is the minimum number of edge rotations needed to transform G into H. The jump and rotation distances of two graphs of the same order and same size are compared. For a set S of graphs of a fixed order at least 5 and fixed size, the jump distance graph $D_j(S)$ of S has S as its vertex set and where G₁ and G₂ in S are adjacent if and only if $d_j(G₁,G₂) = 1$. A graph G is a jump distance graph if there exists a set S of graphs of the same order and same size with $D_j(S) = G$. Several graphs are shown to be jump distance graphs, including all complete graphs, trees, cycles, and cartesian products of jump distance graphs.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Chartrand G.

1 Gavlas H.

1 Hevia H.

1 Johnson M.

1 1997

Wyniki wyszukiwania

Rotation and jump distances between graphs