Paper Info
Title
Embedding graphs of small size
Abstract
An embedding of a graph G ( V, E ) into its complement is a permutation ω on V(G) such that if an edge xy belongs to E(G) then ω( x )ω( y ) does not belong to E(G) . The fact that every graph G of order n and size less than or equal to n −2 is embeddable is well known and has been improved in many ways. We present these improvements which give more information about embeddings than just the existence. The new results (Theorems 1.8, 1.10, 1.12 and 1.13) concern the existence of embeddings σ with restrictions on the cycle length of σ considered as a permutation.
Year
DOI
Venue
1994
10.1016/0166-218X(94)90112-0
Discrete Applied Mathematics
Keywords
Field
DocType
embedding graph,small size
Permutation graph,Graph,Discrete mathematics,Combinatorics,Embedding,Graph embedding,Permutation,Book embedding,Topological graph theory,Mathematics,Complement graph
Journal
Volume
Issue
ISSN
51
1
Discrete Applied Mathematics
Citations 
PageRank 
References 
15
1.45
7
Authors
1
Name
Order
Citations
PageRank
Mariusz Woźniak120434.54