Subgraph distances in graphs defined by edge transfers
type: Item
instance of: scholarly article
title: Subgraph distances in graphs defined by edge transfers
zbMATH Open document ID: 0880.05031
DOI: 10.1016/0012-365X(95)00357-3
author: Gary Chartrand
author: Héctor Hevia
author: Elzbieta B. Jarrett
author: Michelle Schultz
published in: Discrete Mathematics
publication date: 1998-01-19T00:00:00Z
review text: A graph \(G\) and its edge-induced subgraphs having the same number \(k\) of vertices are considered. If \(F\) and \(H\) are such subgraphs, \(H\) is said to be obtained from \(F\) by an edge jump, if there exist four pairwise distinct vertices \(u\), \(v\), \(w\), \(x\) such that \(uv\in E(F)\), \(wx\in E(G)- E(F)\) and \(H= F-uv+wx\). One says that \(F\) can be \(j\)-transformed into \(H\), if \(H\) can be obtained from \(F\) by a finite number of edge jumps. A necessary and sufficient condition for a graph to have the property that any edge-induced subgraph with \(k\) vertices of \(G\) can be \(j\)-transformed into any other one is stated. The \(k\)-jump graph \(J_k(G)\) is defined so that its vertex set is the set of all edge-induced subgraphs of \(G\) with \(k\) vertices and two vertices are adjacent in it if and only if one of them is transformed into the other by one jump. Iterations of the jump graph are studied, it is described when the sequence of such iterations converges, when it diverges and when it terminates. At the end, the hamiltonicity of jump graphs is investigated.
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1047047
zbMATH Keywords: edge jump
zbMATH Keywords: jump graph
zbMATH Keywords: hamiltonicity
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: Graphs whose complement and line graph are isomorphic
cites work: Q4029978
cites work: A metric for graphs
cites work: On distances between isomorphism classes of graphs
cites work: Convergent sequences of iterated \(H\)-line graphs
cites work: Q3976621
cites work: Rotation and jump distances between graphs
cites work: Edge rotations and distance between graphs
cites work: Some Theorems on Abstract Graphs
cites work: On Eulerian and Hamiltonian Graphs and Line Graphs
cites work: Q4871174
cites work: Q3705253
cites work: Mortality of iterated Gallai graphs
cites work: Gallai graphs and anti-Gallai graphs
cites work: The footballers of Croam
full work available at URL: 0012-365x(95)00357-3
OpenAlex ID: W2074065661
Recommended article: Q4029982
Recommended article: Distances between graphs under edge operations
Recommended article: Q3976621
Recommended article: On Distance-Transitive Graphs
Recommended article: Q4661936
Recommended article: Q4343035
Recommended article: On distance subgraphs of graphs in spaces of lower dimensions
Recommended article: On subgraphs in distance-regular graphs
Recommended article: Q4284642
Recommended article: Q4704954
description: scientific article; zbMATH DE number 1047047