×

Negative circles in signed graphs: a problem collection. (English) Zbl 1383.05152

Sinha, Deepa (ed.) et al., International conference on current trends in graph theory and computation, CTGTC-2016, New Delhi, India, September 17–19, 2016. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 63, 41-47 (2017).
Summary: I propose that most problems about circles (cycles, circuits) in ordinary graphs that have odd or even length find their proper setting in the theory of signed graphs, where each edge has a sign, \(+\) or \(-\). Even-circle and odd-circle problems correspond to questions about positive and negative circles in signed graphs. (The sign of a circle is the product of its edge signs.) I outline questions about circles in signed graphs, that seem natural and potentially important.
For the entire collection see [Zbl 1384.05002].

MSC:

05C22 Signed and weighted graphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Behr, Richard, Edges and vertices in a unique signed circle in a signed graph, AKCE Int. J. Graphs Combin. (2017), in press · Zbl 1375.05122
[2] Berge, Claude; Reed, Bruce, Optimal packings of edge-disjoint odd cycles, Discrete Math., 211, 197-202 (2000) · Zbl 0945.05048
[3] Conlon, Joseph G., Even cycles in graphs, J. Graph Theory, 45, 3, 163-223 (2004) · Zbl 1033.05062
[4] Fuita, Shinya; Kawarabayashi, Ken-Ichi, Non-separating even cycles in highly connected graphs, Combinatorica, 30, 5, 565-580 (2010) · Zbl 1231.05146
[5] Harary, F., On local balance and N -balance in signed graphs, Michigan Math. J., 3, 37-41 (1955-56) · Zbl 0070.18502
[6] Winfried, Hochstättler; Nickel, Robert; Peis, Britta, Two disjoint negative cycles in a signed graph, Electronic Notes Discrete Math., 50, 107-111 (2006) · Zbl 1134.05319
[7] Kittipassorn, Teeradej; Mészáros, Gábor, Frustrated triangles, Discrete Math., 338, 12, 2363-2373 (2015) · Zbl 1318.05019
[8] Daniel, Král’; Sereni, Jean-Sébastien; Stacho, Ladislav, Min-max relations for odd cycles in planar graphs, SIAM J. Discrete Math., 26, 3, 884-895 (2012) · Zbl 1256.05119
[9] Marinelli, Fabrizio; Parente, Angelo, A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem, Computers Oper. Res., 69, 68-78 (2016) · Zbl 1349.90819
[10] Popescu, Dragoş-Radu, Proprietati ale grafurilor semnate [Properties of signed graphs], Stud. Cerc. Mat., 31, 43-452 (1979), (in Romanian) · Zbl 0426.05048
[11] Popescu, Dragoş-Radu, Une méthode d’énumération des cycles négatifs d’un graphe signé, Discrete Math., 150, 337-345 (1996) · Zbl 0851.05061
[12] Alex Schaefer, Thomas Zaslavsky, The dimension of the negative cycle vectors of a signed graph, submitted for publication.; Alex Schaefer, Thomas Zaslavsky, The dimension of the negative cycle vectors of a signed graph, submitted for publication. · Zbl 1416.05133
[13] Slilaty, Daniel C., Projective-planar signed graphs and tangled signed graphs, J. Combin. Theory Ser. B, 97, 5, 693-717 (2007) · Zbl 1123.05046
[14] Tomescu, Ioan, Sur le nombre des cycles négatifs d’un graphe complet signé, Math. Sci. Humaines, 53, 63-67 (1976) · Zbl 0327.05119
[15] Truemper, Klaus, Alpha-balanced graphs and matrices and GF(3)-represent-ability of matroids, J. Combin. Theory Ser. B, 32, 112-139 (1982) · Zbl 0478.05026
[16] Tutte, W. T., Graph Theory (2001), Addison-Wesley: Addison-Wesley Reading, Mass.: Cambridge Univ. Press: Addison-Wesley: Addison-Wesley Reading, Mass.: Cambridge Univ. Press Cambridge, Eng., Repr. by · Zbl 0964.05001
[17] Voss, Heinz-Jürgen, Cycles and Bridges in Graphs (1991), Kluwer, Dordrecht, and Deutscher Verlag der Wissenschaften: Kluwer, Dordrecht, and Deutscher Verlag der Wissenschaften Berlin · Zbl 0731.05031
[18] Zaslavsky, Thomas, Characterizations of signed graphs, J. Graph Theory, 5, 401-406 (1981) · Zbl 0471.05035
[19] Zaslavsky, Thomas, Signed graphs, Discrete Appl. Math.. Discrete Appl. Math., Discrete Appl. Math., 5, 248-74 (1983) · Zbl 0503.05060
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.