- Tytuł:
- Rotation and jump distances between graphs
- Autorzy:
-
Chartrand, Gary
Gavlas, Heather
Hevia, Héctor
Johnson, Mark - Powiązania:
- https://bibliotekanauki.pl/articles/972022.pdf
- Data publikacji:
- 1997
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
edge rotation
rotation distance
edge jump
jump distance
jump distance graph - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 285-300
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł