DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 119-134
DOI: 10.7151/dmgt.1089

SOME ADDITIONS TO THE THEORY OF STAR PARTITIONS OF GRAPHS

Francis K. Bell
Mathematics and Statistics Group
Department of Computing Science and Mathematics
University of Stirling, Scotland FK9 4LA
United Kingdom
Dragos Cvetković
Department of Mathematics
Faculty of Electrical Engineering
University of Belgrade
P.O. Box 35-54, 11120 Belgrade
Yugoslavia
Peter Rowlinson
Mathematics and Statistics Group
Department of Computing Science and Mathematics
University of Stirling, Scotland FK9 4LA
United Kingdom
Slobodan K. Simić
Department of Mathematics
Faculty of Electrical Engineering
University of Belgrade
P.O. Box 35-54, 11120 Belgrade
Yugoslavia

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.

Keywords: graph, eigenvalues, eigenspaces, star partitions.

1991 Mathematics Subject Classification: 05C50.

References

[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.
[2] D. Cvetković, Star partitions and the graph isomorphism problem, Linear and Multilinear Algebra 39 (1995) No. 1-2 109-132.
[3] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs (3rd edition, Johann Ambrosius Barth Verlag, Heidelberg, 1995).
[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.
[5] D. Cvetković, P. Rowlinson, S. Simić, Eigenspaces of Graphs (Cambridge University Press, Cambridge, 1997).
[6] D. Cvetković, P. Rowlinson, S.K. Simić, Graphs with least eigenvalue −2: the star complement technique, to appear.
[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.
[8] M.N. Ellingham, Basic subgraphs and graph spectra, Australasian J. Combin. 8 (1993) 247-265.
[9] C.D. Godsil, Matching and walks in graphs, J. Graph Theory 5 (1981) 285-297, doi: 10.1002/jgt.3190050310.
[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).
[11] P. Rowlinson, Dominating sets and eigenvalues of graphs, Bull. London Math. Soc. 26 (1994) 248-254, doi: 10.1112/blms/26.3.248.
[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.
[13] P. Rowlinson, On graphs with multiple eigenvalues, Linear Algebra and Appl. 283 (1998) 75-85, doi: 10.1016/S0024-3795(98)10082-4.
[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] J.J. Seidel, Eutactic stars, in: eds. A. Hajnal and V.T. Sós, Combinatorics (North-Holland, Amsterdam, 1978) 983-999.

Received 4 January 1999
Revised 6 August 1999