Hamiltonicity of complements of middle graphs

DOI10.1016/J.DISC.2006.07.028MaRDI QIDQ870983zbMATH OpenOpenAlexFDO

Authors Xinhui An, Baoyindureng Wu

Publication date 15 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.07.028

zbMATH Keywords

complementHamiltonian graphmiddle graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Review text

Let \(G(V,E)\) be an undirected finite simple graph. The middle graph \(M(G)\) of \(G\) has the vertex set \(V(G)\cup E(G)\) and two vertices \(x,y\) of \(M(G)\) are adjacent in \(M(G)\) if at least one of them corresponds to an edge \(e\) of \(G\) and the other one is either one of the endvertices of \(e\) in \(G\), or corresponds to an edge \(f\) of \(G\) adjacent to \(e\) in \(G\). It is shown that the complement of the middle graph \(M(G)\) is Hamiltonian if and only if \(G\) is not a star and is not isomorphic to one of the graphs \(K_1, 2K_1, K_2, K_1\cup K_2, K_3, K_1\cup K_3\).

Recommendations

• A simple proof of a theorem on complements of middle graphs
• Hamiltonicity of Complements of Total Graphs
• scientific article; zbMATH DE number 3957164
• Energy and Hamiltonicity of graphs
• On the hamiltonian path graph of a graph

Cites work

• A note on Hamiltonian circuits
• Basic properties of total transformation graphs
• Graph theory
• Hamiltonian jump graphs
• Hamiltonian Total Graphs
• scientific article; zbMATH DE number 3675952 (Why is no real title available?)
• scientific article; zbMATH DE number 3790465 (Why is no real title available?)
• On Eulerian and Hamiltonian Graphs and Line Graphs
• Parallel concepts in graph theory
• Subgraph distances in graphs defined by edge transfers
• The transformation graph \(G^{xyz}\) when \(xyz=-++\)
• Traversability and connectivity of the middle graph of a graph

Cited in

(3)

• A simple proof of a theorem on complements of middle graphs
• Hamiltonicity of Complements of Total Graphs
• Domination number and feedback vertex number of complements of line graphs

This page was built for publication: Hamiltonicity of complements of middle graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870983)