Characterization and Construction of Permutation Graphs - Open Journal of Discrete Mathematics

OJDM > Vol.3 No.1, January 2013

Characterization and Construction of Permutation Graphs ()

HTML XML

Download as PDF (Size: 238KB) PP. 33-38

DOI: 10.4236/ojdm.2013.31007 6,667 Downloads 11,717 Views Citations

Author(s)

Severino V. Gervacio, Teofina A. Rapanut, Phoebe Chloe F. Ramos

Affiliation(s)

Department of Mathematics and Computer Science, University of the Philippines, Baguio City, Philippines.
Department of Mathematics, De La Salle University, Manila, Philippines.

ABSTRACT

is a permutation of

, the graph

has vertices

where xy is an edge of

if and only if (x, y) or (y, x) is an inversion of

. Any graph isomorphic to

is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of forbidden induced subgraphs. In 1971 Pnueli, Lempel, and Even showed that a graph is a permutation graph if and only if both the graph and its complement have transitive orientations. In 2010 Limouzy characterized permutation graphs in terms of forbidden Seidel minors. In this paper, we characterize permutation graphs in terms of a cohesive order of its vertices. We show that only the caterpillars are permutation graphs among the trees. A simple method of constructing permutation graphs is also presented here.

KEYWORDS

Permutation; Inversion; Permutation Graph; Cohesive Order; Oriented Graph; Tournament Score Sequence; Caterpillar; Graph Composition

Share and Cite:

S. Gervacio, T. Rapanut and P. Ramos, "Characterization and Construction of Permutation Graphs," Open Journal of Discrete Mathematics, Vol. 3 No. 1, 2013, pp. 33-38. doi: 10.4236/ojdm.2013.31007.

Journals Menu

Follow SCIRP

	+1 323-425-8868
	customer@scirp.org
	+86 18163351462(WhatsApp)
	1655362766

	Paper Publishing WeChat

Journals Menu

Home

About SCIRP

Service

Policies