Pseduosimilar Vertices in a Graph.
Abstract
Dissimilar vertices whose removal leaves isomorphic subgraphs are called pseudosimilar. We construct infinite families of graphs having identity automorphism group, yet every vertex is pseudosimilar to some other vertex. Potential impact on the Reconstruction Conjecture is considered. We also construct, for each n, graphs containing a subset of vertices of size n which are mutually pseudosimilar. The analogous problem for mutually pseudosimilar edges is introduced. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1980
- Accession Number
- ADA085746
Entities
People
- Allen J. Schwenk
- Paul K. Stockmeyer
- Robert J. Kimble Jr.
Organizations
- College of William & Mary