Multiple Petersen subdivisions in permutation graphs

MaRDI QIDQ1953423zbMATH OpenFDO

Authors Tomáš Kaiser, Jean-Sébastien Sereni, Zelealem B. Yilma

Publication date 7 June 2013

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.1989, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p37

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cographpermutation graphPetersen subdivision

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph theory (05C99)

Abstract: A permutation graph is a cubic graph admitting a 1-factor M whose complement consists of two chordless cycles. Extending results of Ellingham and of Goldwasser and Zhang, we prove that if e is an edge of M such that every 4-cycle containing an edge of M contains e, then e is contained in a subdivision of the Petersen graph of a special type. In particular, if the graph is cyclically 5-edge-connected, then every edge of M is contained in such a subdivision. Our proof is based on a characterization of cographs in terms of twin vertices. We infer a linear lower bound on the number of Petersen subdivisions in a permutation graph with no 4-cycles, and give a construction showing that this lower bound is tight up to a constant factor.

Review text

Summary: A permutation graph is a cubic graph admitting a 1-factor \(M\) whose complement consists of two chordless cycles. Extending results of \textit{M. N. Ellingham} [Congr. Numerantium 44, 33--40 (1984; Zbl 0558.05040)] and of \textit{J. L. Goldwasser} and \textit{C.-Q. Zhang} [Ars Comb. 51, 240--248 (1999; Zbl 0977.05067)], we prove that if \(e\) is an edge of \(M\) such that every 4-cycle containing an edge of \(M\) contains \(e\), then \(e\) is contained in a subdivision of the Petersen graph of a special type. In particular, if the graph is cyclically 5-edge-connected, then every edge of \(M\) is contained in such a subdivision. Our proof is based on a characterization of cographs in terms of twin vertices. We infer a linear lower bound on the number of Petersen subdivisions in a permutation graph with no 4-cycles, and give a construction showing that this lower bound is tight up to a constant factor.

Recommendations

• Permutation graphs and Petersen graph
• scientific article; zbMATH DE number 1052840
• A Petersen on a pentagon
• Generalized Petersen graphs which are cycle permutation graphs
• scientific article; zbMATH DE number 622475

Cited in

(1)

• Permutation graphs and Petersen graph

This page was built for publication: Multiple Petersen subdivisions in permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1953423)