𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the embedding of graphs into graphs with few eigenvalues

✍ Scribed by Vu, Van H.

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
726 KB
Volume
22
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic graphs of type k for every k 2 3. Furthermore, in the case k 2 5 such a family of extensions can be found at every sufficiently large order. Some bounds for the extension will also be given. 0 1996

πŸ“œ SIMILAR VOLUMES

On the second largest eigenvalue of line
On the second largest eigenvalue of line graphs
✍ Petrovi?, Miroslav; Mileki?, Bojana πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 169 KB πŸ‘ 2 views

In this paper all connected line graphs whose second largest eigenvalue does not exceed 1 are characterized. Besides, all minimal line graphs with second largest eigenvalue greater than 1 are determined.

On the number of triangular embeddings o
On the number of triangular embeddings of complete graphs and complete tripartite graphs
✍ M. J. Grannell; M. Knor πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 159 KB

## Abstract We prove that for every prime number __p__ and odd __m__>1, as __s__β†’βˆž, there are at least __w__ face 2‐colorable triangular embeddings of __K__~__w, w, w__~, where __w__ = __m__Β·__p__^__s__^. For both orientable and nonorientable embeddings, this result implies that for infinitely many

On the Connectivity of Graphs Embedded i
On the Connectivity of Graphs Embedded in Surfaces
✍ Michael D Plummer; Xiaoya Zha πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 376 KB

In a 1973 paper, Cooke obtained an upper bound on the possible connectivity of a graph embedded in a surface (orientable or nonorientable) of fixed genus. Furthermore, he claimed that for each orientable genus #>0 (respectively, nonorientable genus #Γ„ >0, #Γ„ {2) there is a complete graph of orientab

The Order Upper Bound on Parity Embeddin
The Order Upper Bound on Parity Embedding of a Graph
✍ Thomas Zaslavsky πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 398 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according to whether its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is the Euler characteristic) over all surfaces S in which 1 can be parity embedde