Embedding graphs of small size
type: Item
instance of: scholarly article
title: Embedding graphs of small size
zbMATH Open document ID: 0807.05025
DOI: 10.1016/0166-218X(94)90112-0
author: Mariusz Woźniak
published in: Discrete Applied Mathematics
publication date: 1994-07-31T00:00:00Z
review text: An embedding \(\sigma\) of a graph \(G\) into its complement \(\overline G\) is a permutation of \(V(G)\) such that if \(xy\in E(G)\) then \(\sigma(x)\sigma(y)\in E(\overline G)\). \textit{D. Burns} and \textit{S. Schuster} [J. Graph Theory 1, 277-279 (1977; Zbl 0375.05046)] proved that if \(G\) is a graph of order \(n\) and \(| E(G)|\leq n- 2\), then \(G\) can be embedded into its complement \(\overline G\). This theorem had been generalized/improved in several different directions. This paper gives four further generalizations/improvements.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 612448
zbMATH Keywords: packing
zbMATH Keywords: embedding
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: On self‐complementation
cites work: Q3852212
cites work: Q4097326
cites work: Every (p,p-2) graph is contained in its complement
cites work: Embedding graphs in their complements
cites work: Mutual placement of bipartite graphs
cites work: Selbstkomplementäre Graphen
cites work: Q5730676
cites work: Edge disjoint placement of graphs
cites work: Fixed-point-free embeddings of graphs in their complements
cites work: Triple placement of graphs
cites work: Q3137222
cites work: Q4027203
cites work: Q3715121
cites work: Packing of graphs - a survey
description: scientific article; zbMATH DE number 612448