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:; Daniela Ferrero, Department of Mathematics, Texas State University, San Marcos, TX $78666$, USA, e-mail:; Ralucca Gera, Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA $93943$, USA, e-mail:; Eunjeong Yi, Department of General Academics, Texas A&M University at Galveston, Galveston, TX 77553, USA, e-mail:

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.

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at

[Previous Article] [Next Article] [Contents of This Number] [Contents of Mathematica Bohemica]
[Full text of the older issues of Mathematica Bohemica at DML-CZ]