Paper Info
Title
Stratified graphs for imbedding systems
Abstract
Two imbeddings of a graph G are considered to be adjacent if the second can be obtained from the first by moving one or both ends of a single edge within its or their respective rotations. Thus, a collection of imbeddings S of G , called a ‘system’, may be represented as a ‘stratified graph’, and denoted SG ; the focus here is the case in which S is the collection of all orientable imbeddings. The induced subgraph of SG on the set of imbeddings into the surface of genus k is called the ‘ k th stratum’, and the cardinality of that set of imbeddings is called the ‘stratum size’; one may observe that the sequence of stratum sizes is precisely the genus distribution for the graph G . It is known that the genus distribution is not a complete invariant, even when the category of graphs is restricted to be simplicial and 3-connected. However, it is proved herein that the link of each point — that is, the subgraph induced by its neighbors — of SG is a complete isomorphism invariant for the category of graphs whose minimum valence is at least three. This supports the plausibility of a probabilistic approach to graph isomorphism testing by sampling higher-order imbedding distribution data. A detailed structural analysis of stratified graphs is presented.
Year
DOI
Venue
1995
10.1016/0012-365X(94)00029-I
Discrete Mathematics
Keywords
Field
DocType
stratified graph,imbedding system,higher order,graph isomorphism,structure analysis
Discrete mathematics,Combinatorics,Line graph,Graph isomorphism,Forbidden graph characterization,Graph homomorphism,Induced subgraph,Induced subgraph isomorphism problem,Cograph,Universal graph,Mathematics
Journal
Volume
Issue
ISSN
143
1-3
Discrete Mathematics
Citations 
PageRank 
References 
0
0.34
11
Authors
2
Name
Order
Citations
PageRank
Jonathan L. Gross1458268.73
Thomas W. Tucker2191130.07