IJPAM: Volume 108, No. 2 (2016)

ON PLANARITY OF $3$-JUMP GRAPHS

Varanoot Khemmani$^1$, Chira Lumduanhom$^2$,
Sriwan Muangloy$^3$, Massiri Muanphet$^4$, Kittisak Tipnuch$^5$
$^{1,2,3,4,5}$Department of Mathematics
Srinakharinwirot University
Sukhumvit 23, Bangkok, 10110, THAILAND

Abstract. For a graph $G$ of size $m \ge 1$ and edge-induced subgraphs $F$ and $H$ of size $k$ where $1 \le k \le m$, the subgraph $H$ is said to be obtained from the subgraph $F$ by an edge jump if there exist four distinct vertices $u$, $v$, $w$ and $x$ such that $uv \in E(F)$, $wx \in E(G) - E(F)$, and $H = F - uv + wx$. The $k$-jump graph $J_{k}(G)$ is that graph whose vertices correspond to the edge-induced subgraphs of size $k$ of $G$ where two vertices $F$ and $H$ of $J_{k}(G)$ are adjacent if and only if $H$ can be obtained from $F$ by an edge jump.

All connected graphs $G$ for whose $J_{3}(G)$ is planar are determined.

Received: January 27, 2016

Revised: January 27, 2016

Published: October 1, 2016

AMS Subject Classification: 05C10, 05C12

Key Words and Phrases: $k$-jump distance, $k$-jump graph, $3$-jump graph, planar graph
Download paper from here.

Bibliography

1
G. Chartrand, H. Hevia, E.B. Jarrett and M. Schultz, Subgraph distance in graphs defined by edge tranfers, Discrete Math., 170 (1997), 63-79.

2
G. Chartrand, L. Lesniak and P. Zhang,Graphs & Digraphs: 5th Edition,Chapman & Hall/CRC, USA (2010).

3
H. Hevia, D.W. VanderJagt, and P. Zhang, On the planarity of jump graphs, Discrete Math., 220 (2000), 119-129.

4
K. Kuratowski, Sur le probléme des courbes gauches en topologie, Fund. Math., 15 (1930), 270-283.

.




DOI: 10.12732/ijpam.v108i2.18 How to cite this paper?

Source:
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 108
Issue: 2
Pages: 451 - 466


$3$-JUMP GRAPHS%22&as_occt=any&as_epq=&as_oq=&as_eq=&as_publication=&as_ylo=&as_yhi=&as_sdtAAP=1&as_sdtp=1" title="Click to search Google Scholar for this entry" rel="nofollow">Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).