Some additions to the theory of star partitions of graphs

Francis K. Bell; Dragos Cvetković; Peter Rowlinson; Slobodan K. Simić

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 2, page 119-134
  • ISSN: 2083-5892

Abstract

top
This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.

How to cite

top

Francis K. Bell, et al. "Some additions to the theory of star partitions of graphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 119-134. <http://eudml.org/doc/270753>.

@article{FrancisK1999,
abstract = {This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.},
author = {Francis K. Bell, Dragos Cvetković, Peter Rowlinson, Slobodan K. Simić},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; eigenvalues; eigenspaces; star partitions; galaxy graphs; star set},
language = {eng},
number = {2},
pages = {119-134},
title = {Some additions to the theory of star partitions of graphs},
url = {http://eudml.org/doc/270753},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Francis K. Bell
AU - Dragos Cvetković
AU - Peter Rowlinson
AU - Slobodan K. Simić
TI - Some additions to the theory of star partitions of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 2
SP - 119
EP - 134
AB - This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.
LA - eng
KW - graph; eigenvalues; eigenspaces; star partitions; galaxy graphs; star set
UR - http://eudml.org/doc/270753
ER -

References

top
  1. [1] G. Caporossi, D. Cvetković, P. Hansen, S. Simić, Variable neighborhood search for extremal graphs, 3: on the largest eigenvalue of color-constrained trees, to appear. Zbl1003.05058
  2. [2] D. Cvetković, Star partitions and the graph isomorphism problem, Linear and Multilinear Algebra 39 (1995) No. 1-2 109-132. Zbl0831.05043
  3. [3] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs (3rd edition, Johann Ambrosius Barth Verlag, Heidelberg, 1995). Zbl0824.05046
  4. [4] D. Cvetković, M. Petrić, A table of connected graphs on six vertices, Discrete Math. 50 (1984) 37-49, doi: 10.1016/0012-365X(84)90033-5. Zbl0533.05052
  5. [5] D. Cvetković, P. Rowlinson, S. Simić, Eigenspaces of Graphs (Cambridge University Press, Cambridge, 1997). Zbl0878.05057
  6. [6] D. Cvetković, P. Rowlinson, S.K. Simić, Graphs with least eigenvalue -2: the star complement technique, to appear. Zbl0982.05065
  7. [7] M. Doob, An inter-relation between line graphs, eigenvalues and matroids, J. Combin. Theory (B) 15 (1973) 40-50, doi: 10.1016/0095-8956(73)90030-0. Zbl0245.05125
  8. [8] M.N. Ellingham, Basic subgraphs and graph spectra, Australasian J. Combin. 8 (1993) 247-265. Zbl0790.05057
  9. [9] C.D. Godsil, Matching and walks in graphs, J. Graph Theory 5 (1981) 285-297, doi: 10.1002/jgt.3190050310. 
  10. [10] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy Kan, D.B. Schmoys, eds., The traveling salesman problem (John Wiley and Sons, Chichester - New York - Brisbane - Toronto - Singapore, 1985). Zbl0563.90075
  11. [11] P. Rowlinson, Dominating sets and eigenvalues of graphs, Bull. London Math. Soc. 26 (1994) 248-254, doi: 10.1112/blms/26.3.248. Zbl0806.05040
  12. [12] P. Rowlinson, Star sets and star complements in finite graphs: a spectral construction technique, in: Proc. DIMACS Workshop on Discrete Mathematical Chemistry (March 1998), to appear. Zbl0964.05041
  13. [13] P. Rowlinson, On graphs with multiple eigenvalues, Linear Algebra and Appl. 283 (1998) 75-85, doi: 10.1016/S0024-3795(98)10082-4. Zbl0931.05055
  14. [14] P. Rowlinson, Linear Algebra, in: eds. L.W. Beineke and R.J. Wilson, Graph Connections (Oxford Lecture Series in Mathematics and its Applications 5, Oxford University Press, Oxford, 1997) 86-99. 
  15. [15] J.J. Seidel, Eutactic stars, in: eds. A. Hajnal and V.T. Sós, Combinatorics (North-Holland, Amsterdam, 1978) 983-999. Zbl0391.05050

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.