MATHEMATICA BOHEMICA, Vol. 136, No. 1, pp. 27-37, 2011

# Functigraphs: An extension of permutation graphs

## Andrew Chen, Daniela Ferrero, Ralucca Gera, Eunjeong Yi

Andrew Chen, Department of Computer Science and Information Systems, Minnesota State University Moorhead, Moorhead, MN $56563$, USA, e-mail: chenan@mnstate.edu; Daniela Ferrero, Department of Mathematics, Texas State University, San Marcos, TX $78666$, USA, e-mail: dferrero@txstate.edu; Ralucca Gera, Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA $93943$, USA, e-mail: rgera@nps.edu; Eunjeong Yi, Department of General Academics, Texas A&M University at Galveston, Galveston, TX 77553, USA, e-mail: yie@tamug.edu

Abstract: Let $G_1$ and $G_2$ be copies of a graph $G$, and let $f V(G_1) \rightarrow V(G_2)$ be a function. Then a functigraph $C(G, f)=(V, E)$ is a generalization of a permutation graph, where $V=V(G_1) \cup V(G_2)$ and $E=E(G_1) \cup E(G_2)\cup\{uv u \in V(G_1), v \in V(G_2),v=f(u)\}$. In this paper, we study colorability and planarity of functigraphs.

Keywords: permutation graph, generalized Petersen graph, functigraph

Classification (MSC 2010): 05C15, 05C10

Full text available as PDF.