𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some characterizations of graphs by star complements

✍ Scribed by Dragoš Cvetković; Peter Rowlinson; Slobodan K. Simić

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
158 KB
Volume
301
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

✦ Synopsis

Let µ be an eigenvalue of the graph G with multiplicity k. A star complement for µ in G is an induced subgraph H = G -X such that |X| = k and µ is not an eigenvalue of G -X. Various graphs related to (generalized) line graphs or their complements are characterized by star complements corresponding to eigenvalues -2 or 1.

📜 SIMILAR VOLUMES

Some parameters of graph and its complem
Some parameters of graph and its complement
✍ Shao-ji Xu 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 627 KB

In this paper, we have discussed the Nordhaus-Gaddum problems for diameter d, girth g, circumference c and edge covering number ill-We have both got the following results. If both G and G are connected, then 4<~d+a~~ 6, then p+2<.c+~<.2p, 3(p-1)<~c.~<.p 2. If both G and G have no isolated vertex, th

On the edge-integrity of some graphs and
On the edge-integrity of some graphs and their complements
✍ R. Laskar; S. Stuecle; B. Piazza 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 483 KB

In this paper the authors study the edge-integrity of graphs. Edge-integrity is a very useful measure of the vulnerability of a network, in particular a communication network, to disruption through the deletion of edges. A number of problems are examined, including some Nordhaus-Gaddum type results.

Star chromatic numbers of some planar gr
Star chromatic numbers of some planar graphs
✍ Gao, Guogang; Wang, Yiju; Zhou, Huishan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 2 views

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551--559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of pla