×

Eigenvalues and clique partitions of graphs. (English) Zbl 1468.05175

Summary: A clique partition \(\epsilon\) of graph \(G\) is a set of cliques such that each edge of \(G\) belongs to exactly one clique, and the total size of \(\epsilon\) is the sum of cardinalities of all elements in \(\epsilon \). The \(\epsilon \)-degree of a vertex \(u\) is the number of cliques in \(\epsilon\) containing \(u\). We say that \(\epsilon\) is a \(k\)-restricted clique partition if each vertex has \(\epsilon \)-degree at least \(k\). The \((k\)-restricted) clique partition number of \(G\) is the smallest cardinality of a (\(k\)-restricted) clique partition of \(G\). In this paper, we obtain eigenvalue bounds for \(\epsilon \)-degrees, clique partition number and restricted clique partition number of a graph. As applications, we derive the De Bruijn-Erdős Theorem from our eigenvalue bounds, obtain accurate estimation of the 2-restricted clique partition number of line graphs, and give spectral lower bounds for the minimum total size of clique partitions of a graph.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] de Bruijn, N. G.; Erdős, P., On a combinatorial problem, Indag. Math., 10, 421-423 (1948)
[2] Chung, F. R.K., On the decomposition of graphs, SIAM J. Algebraic Discrete Methods, 2, 1-12 (1981) · Zbl 0499.05046
[3] Cioabă, S. M.; Haemers, W. H.; Vermette, J.; Wong, W., The graphs with all but two eigenvalues equal to ±1, J. Algebraic Comb., 41, 887-897 (2015) · Zbl 1317.05111
[4] Cvetković, D.; Rowlinson, P.; Simić, S., An Introduction to the Theory of Graph Spectra (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1211.05002
[5] Erdős, P.; Faudree, R.; Ordman, E. T., Clique partitions and clique coverings, Discrete Math., 72, 93-101 (1988) · Zbl 0679.05040
[6] Erdős, P.; Goodman, A. W.; Pósa, L., The representation of a graph by set intersections, Can. J. Math., 18, 106-112 (1966) · Zbl 0137.43202
[7] Ghorbani, E.; Maimani, H. R., On eigensharp and almost eigensharp graphs, Linear Algebra Appl., 429, 2746-2753 (2008) · Zbl 1171.05033
[8] Graham, R. L.; Pollak, H. O., On the addressing problem for loop switching, Bell Syst. Tech. J., 50, 2495-2519 (1971) · Zbl 0228.94020
[9] Graham, R. L.; Pollak, H. O., On embedding graphs in squashed cubes, (Graph Theory and Applications. Graph Theory and Applications, Lecture Notes in Math., vol. 303 (1972), Springer: Springer Berlin), 99-110 · Zbl 0251.05123
[10] Gregory, D. A.; Heyink, B.; Vander Meulen, K. N., Inertia and biclique decompositions of joins of graphs, J. Comb. Theory, Ser. B, 88, 135-151 (2003) · Zbl 1025.05042
[11] Gregory, D. A.; McGuinness, S.; Wallis, W., Clique partitions of the cocktail party graph, Discrete Math., 59, 267-273 (1986) · Zbl 0594.05039
[12] Gregory, D. A.; Vander Meulen, K. N., Sharp bounds for decompositions of graphs into complete r-partite subgraphs, J. Graph Theory, 21, 393-400 (1996) · Zbl 0856.05081
[13] Gregory, D. A.; Shader, B. L.; Watts, V. L., Biclique decompositions and Hermitian rank, Linear Algebra Appl., 292, 267-280 (1999) · Zbl 0929.05056
[14] Gutman, I., The energy of a graph, Ber. Math.-Stat. Sekt. Forsch-Zent. Graz, 103, 1-22 (1978) · Zbl 0402.05040
[15] Győri, E.; Kostochka, A. V., On a problem of G.O.H. Katona and T. Tarján, Acta Math. Acad. Sci. Hung., 34, 321-327 (1979) · Zbl 0463.05054
[16] Hoffman, A. J., Eigenvalues and partitionings of the edges of a graph, Linear Algebra Appl., 5, 137-146 (1972) · Zbl 0247.05125
[17] Kahn, J., Proof of a conjecture of Katona and Tarján, Period. Math. Hung., 12, 81-82 (1981) · Zbl 0429.05049
[18] Král’, D.; Lidický, B.; Martins, T. L.; Pehova, Y., Decomposing graphs into edges and triangles, Comb. Probab. Comput., 28, 465-472 (2019) · Zbl 1436.05086
[19] Kratzke, T.; Reznick, B.; West, D., Eigensharp graphs: decomposition into complete bipartite subgraphs, Trans. Am. Math. Soc., 308, 637-653 (1988) · Zbl 0652.05037
[20] McGuinness, S.; Rees, R., On the number of distinct minimal clique partitions and clique covers of a line graph, Discrete Math., 83, 49-62 (1990) · Zbl 0739.05049
[21] Orlin, J., Contentment in graph theory: covering graphs with cliques, Indag. Math., 39, 406-424 (1977) · Zbl 0374.05041
[22] Peck, G. W., A new proof of a theorem of Graham and Pollak, Discrete Math., 49, 327-328 (1984) · Zbl 0533.05049
[23] Rowlinson, P., Certain 3-decompositions of complete graphs, with an application to finite fields, Proc. R. Soc. Edinb., 99A, 277-281 (1985) · Zbl 0562.05044
[24] Sawa, M., On a symmetric representation of Hermitian matrices and its applications to graph theory, J. Comb. Theory, Ser. B, 116, 484-503 (2016) · Zbl 1327.05281
[25] Schwenk, A. J.; Lossers, O. P., Solution to advanced problem #6434, Am. Math. Mon., 94, 885-886 (1987)
[26] Tverberg, H., On the decomposition of \(K_n\) into complete bipartite graphs, J. Graph Theory, 6, 493-494 (1982) · Zbl 0502.05048
[27] Vishwanathan, S., A polynomial space proof of the Graham-Pollak theorem, J. Comb. Theory, Ser. A, 115, 674-676 (2008) · Zbl 1146.05309
[28] Wallis, W. D., Asymptotic values of clique partition numbers, Combinatorica, 2, 99-101 (1982) · Zbl 0492.05042
[29] Zhou, J.; Sun, L.; Yao, H.; Bu, C., On the nullity of connected graphs with least eigenvalue at least -2, Appl. Anal. Discrete Math., 7, 250-261 (2013) · Zbl 1313.05260
[30] Zhou, J.; Bu, C., The enumeration of spanning tree of weighted graphs, J. Algebraic Comb. (2020)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.