×

Extremal results for \(C_3^-\)-free signed graphs. (English) Zbl 1539.05087

A signed graph \((G,\sigma)\) is a graph \(G\) equipped with a signature \(\sigma\), which assigns to each edge of \(G\) a sign (either \(+\) or \(-\) ). In extremal graph theory, the Turán problem is a significant one that involves finding out the exact value of the Turán number \(\operatorname{ex}(n, H)\). However, determining the Turán number is not a straightforward exercise. The paper discusses the spectral analogues of the Turán type problem for signed graphs, focusing on finding the maximum spectral radius among all \(n\)-vertex \(H\)-free graphs. The main findings are if \(\dot{G}\) is \(C^{-}_{3}\)-free, then \(e(\dot{G}) \leq \frac{n(n-1)}{2}-(n-2)\) and \(\rho(\dot{G})\leq \frac{1}{2}(\sqrt(n^{2}-8)+n-4)\) and equality holds in case when \(\dot{G}\) is switching equivalent to \(\dot{G}^{s,t}\) and \(\dot{G}^{1,n-3}\), respectively. The study revolves around the (spectral) Turán problem in \(C^{-}_{3}\)-free signed graphs with \(n\) vertices and the methodology is a blend of spectral analogues of the parameters of signed graphs.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C22 Signed and weighted graphs
05C35 Extremal problems in graph theory
05C30 Enumeration in graph theory
Full Text: DOI

References:

[1] Akbari, S.; Belardo, F.; Heydari, F.; Maghasedi, M.; Souri, M., On the largest eigenvalue of signed unicyclic graphs. Linear Algebra Appl., 145-162 (2019) · Zbl 1420.05070
[2] Babai, L.; Guiduli, B., Spectral extrema for graphs: the Zarankiewicz problem. Electron. J. Comb. (2009), #R123 · Zbl 1186.05079
[3] Belardo, F.; Brunetti, M.; Ciampella, A., Unbalanced unicyclic and bicyclic graphs with extremal spectral radius. Czechoslov. Math. J., 2, 417-433 (2021) · Zbl 1513.05238
[4] Belardo, F.; Cioabă, S.; Koolen, J.; Wang, J., Open problems in the spectral theory of signed graphs. Art Discrete Appl. Math. (2018) · Zbl 1421.05052
[5] Bondy, J. A., Large cycles in graphs. Discrete Math., 121-132 (1971) · Zbl 0224.05120
[6] Bondy, J. A., Pancyclic graphs I. J. Comb. Theory, Ser. B, 80-84 (1971) · Zbl 0183.52301
[7] Bondy, J. A.; Simonovits, M., Cycles of even length in graphs. J. Comb. Theory, Ser. B, 97-105 (1974) · Zbl 0283.05108
[8] Brouwer, A. E.; Haemers, W. H., Spectra of Graphs (2011), Springer
[9] Brunetti, M.; Ciampella, A., Signed bicyclic graphs with minimal index. Commun. Comb. Optim., 1, 207-241 (2023) · Zbl 1524.05126
[10] Brunetti, M.; Stanić, Z., Unbalanced signed graphs with extremal spectral radius or index. Comput. Appl. Math., 118 (2022) · Zbl 1499.05257
[11] Brunetti, M.; Stanić, Z., Ordering signed graphs with large index. Ars Math. Contemp., 4 (2022), #P4.05 · Zbl 1497.05109
[12] Bussemaker, F. C.; Cameron, P. J.; Seidel, J. J.; Tsaranov, S. V., Tables of signed graphs (1991), Eut Report 91-WSK-01, Eindhoven
[13] Füredi, Z., On the number of edges of quadrilateral-free graphs. J. Comb. Theory, Ser. B, 1-6 (1996) · Zbl 0858.05063
[14] Füredi, Z.; Gunderoson, D. S., Extremal numbers for odd cycles. Comb. Probab. Comput., 641-645 (2015) · Zbl 1371.05142
[15] Füredi, Z.; Naor, A.; Verstrae̋te, J., On the Turán number for the hexagon. Adv. Math., 476-496 (2006) · Zbl 1094.05032
[16] He, C.; Li, Y.; Shan, H.; Wang, W., On the index of unbalanced signed bicyclic graphs. Comput. Appl. Math., 124 (2021) · Zbl 1476.05117
[17] Huang, H., Induced graphs of the hypercube and a proof of the Sensitivity Conjecture. Ann. Math., 949-955 (2019) · Zbl 1427.05116
[18] Nikiforov, V., Some inequalities for the largest eigenvalue of a graph. Comb. Probab. Comput., 179-189 (2002) · Zbl 1005.05029
[19] Nikiforov, V., The spectral radius of graphs without paths and cycles of specified length. Linear Algebra Appl., 2243-2256 (2010) · Zbl 1217.05152
[20] Nikiforov, V., Bounds on graph eigenvalues II. Linear Algebra Appl., 183-189 (2007) · Zbl 1128.05035
[21] Stanić, Z., Bounding the largest eigenvalue of signed graphs. Linear Algebra Appl., 80-89 (2019) · Zbl 1411.05109
[22] Stanić, Z., Some bounds for the largest eigenvalue of a signed graph. Bull. Math. Soc. Sci. Math. Roum., 110, 183-189 (2019) · Zbl 1463.05237
[23] Sun, G.; Liu, F.; Lan, K., A note on eigenvalues of signed graphs. Linear Algebra Appl., 125-131 (2022) · Zbl 1496.05101
[24] Turán, P., On the theory of graphs. Colloq. Math., 19-30 (1954) · Zbl 0055.17004
[25] Wilf, H., Spectral bounds for the clique and independence numbers of graphs. J. Comb. Theory, Ser. B, 113-117 (1986) · Zbl 0598.05047
[26] Zhai, M.; Lin, H., Spectral extrema of graphs: forbidden hexagon. Discrete Math., 10 (2020) · Zbl 1445.05055
[27] Zhai, M.; Liu, R.; Xue, J., A unique characterization of spectral extrema for friendship graphs. Electron. J. Comb., 3 (2022), #P3.32 · Zbl 1496.05107
[28] Zhai, M.; Wang, B., Proof of a conjecture on the spectral radius of \(C_4\)-free graphs. Linear Algebra Appl., 1641-1647 (2012) · Zbl 1247.05145
[29] Zaslavsky, T., Signed graphs. Discrete Appl. Math., 47-74 (1982) · Zbl 0476.05080
[30] Zaslavsky, T., Matrices in the theory of signed simple graphs, 207-229 · Zbl 1231.05120
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.