2022/06/06 by Ashok Kumar Das, Das, Ashok Kumar, Indrajit Paul +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2206.02385
openalex publication_date 2022/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is Hamiltonian-connected if there exists a Hamiltonian path between any two vertices of G. It is known that if G is 2-connected then the graph G2 is Hamiltonian-connected. In this paper we prove that the square of every self-complementary graph of order grater than 4 is Hamiltonian-connected. If G is a k-critical graph, then we prove that the Mycielski graph μ(G) is (k+1)-critical graph. Jarnicki et al.[7] proved that for every Hamiltonian graph of odd order, the Mycielski graph μ(G) of G is Hamiltonian-connected. They also pose a conjecture that if G is Hamiltonian-connected and not K2 then μ(G) is Hamiltonian-connected. In this paper we also prove this conjecture.