Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
permutation graph; generalized Petersen graph; functigraph
permutation graph; generalized Petersen graph; functigraph
Summary:
Let $G_1$ and $G_2$ be copies of a graph $G$, and let $f\colon 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 \colon u \in V(G_1), v \in V(G_2),v=f(u)\}$. In this paper, we study colorability and planarity of functigraphs.
References:
[1] Chartrand, G., Frechen, J. B.: On the chromatic number of permutation graphs. Proof Tech. Graph Theory, Proc. 2nd Ann Arbor Graph Theory Conf. 1968 21-24 (1969). MR 0250934 | Zbl 0199.59401
[2] Chartrand, G., Harary, F.: Planar permutation graphs. Ann. Inst. Henri. Poincaré, Nouv. Sér., Sect. B 3 433-438 (1967). MR 0227041 | Zbl 0162.27605
[3] Chartrand, G., Zhang, P.: Introduction to Graph Theory. McGraw-Hill, Kalamazoo, MI (2004).
[4] Hedetniemi, S.: On classes of graphs defined by special cutsets of lines. Many Facets of Graph Theory, Proc. Conf. Western Michigan Univ., Kalamazoo/Mi. 1968, Lect. Notes Math. 110 171-189 (1969). DOI 10.1007/BFb0060115 | MR 0250921 | Zbl 0191.54905
[5] Judson, T. W.: Abstract Algebra: theory and applications. Boston, MA: PWS Publishing Company (1994). Zbl 0823.00002
Search
Partner of
