Negative (and positive) circles in signed graphs: A problem collectionFootnote

Peer review under responsibility of Kalasalingam University.

References

• König Dénes Theorie der endlichen und unendlichen Graphen 1936 Akademische Verlagsgesellschaft Leipzig Repr. Chelsea, New York, 1950
   Google Scholar
• Zaslavsky Thomas Biased graphs. I. Bias, balance, and gains J. Combin. Theory Ser. B 47 1989 32 52
   Web of Science ®Google Scholar
• Harary F. On the notion of balance of a signed graph Michigan Math. J. 2 1953–54 143 146 and addendum preceding p. 1
   Google Scholar
• Harary F. Structural duality Behav. Sci. 2 1957 255 265
   Google Scholar
• Zaslavsky Thomas Characterizations of signed graphs J. Graph Theory 5 1981 401 406
   Web of Science ®Google Scholar
• Sozański Tadeusz Enumeration of weak isomorphism classes of signed graphs J. Graph Theory 4 1980 127 144
   Web of Science ®Google Scholar
• Pierre Hansen, Labelling algorithms for balance in signed graphs, in: Problèmes Combinatoires et Theorie des Graphes (Colloq. Int., Orsay, 1976), pp. 215–217. Colloques Int. du CNRS, 260. Editions du C.N.R.S. Paris, 1978.
   Google Scholar
• Harary Frank Kabell Jerald A. A simple algorithm to detect balance in signed graphs Math. Soc. Sci. 1 1980/81 131 136
   Web of Science ®Google Scholar
• Zaslavsky Thomas Vertices of localized imbalance in a biased graph Proc. Amer. Math. Soc. 101 1987 199 204
   Web of Science ®Google Scholar
• Zaslavsky Thomas Biased graphs. II. The three matroids J. Combin. Theory Ser. B 51 1991 46 72
   Web of Science ®Google Scholar
• Wm Shakespeare, King Lear. Various editions.
   Google Scholar
• Akiyama J. Avis D. Chvátal V. Era H. Balancing signed graphs Discrete Appl. Math. 3 1981 227 233
   Web of Science ®Google Scholar
• Petersdorf M. Einige bemerkungen über vollständige Bigraphen Wiss. Z. Techn. Hochsch, Ilmenau 12 1966 257 260
   Google Scholar
• Barahona Francisco On the computational complexity of Ising spin glass models J. Phys. A: Math. Gen. 15 1982 3241 3253
   Google Scholar
• Choi Hyeong-Ah Nakajima Kazuo Rim Chong S. Graph bipartization and via minimization SIAM J. Discrete Math. 2 1 1989 38 47
   Google Scholar
• Vogel E.E. Cartes J. Contreras S. Lebrecht W. Villegas J. Ground-state properties of finite square and triangular Ising lattices with mixed exchange interactions Phys. Rev. B 49 9 1994 6018 6027
   Web of Science ®Google Scholar
• Hartmann Alexander K. Ground states of two-dimensional Ising spin glasses: Fast algorithms, recent developments and a ferromagnet-spin glass mixture J. Stat. Phys. 144 2011 519 540
   Web of Science ®Google Scholar
• Berge Claude Reed Bruce Edge-disjoint odd cycles in graphs with small chromatic number Symposium à la Mémoire de François Jaeger (Grenoble, 1998) Ann. Inst. Fourier (Grenoble) 49 1999 783 786
   Google Scholar
• Behr Richard Edges and vertices in a unique signed circle in a signed graph AKCE Int. J. Graphs Comb. 14 3 2017 224 232
   Web of Science ®Google Scholar
• Marinelli Fabrizio Parente Angelo A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem Comput. Oper. Res. 69 2016 68 78
   Web of Science ®Google Scholar
• Harary F. On local balance and N-balance in signed graphs Michigan Math. J. 3 1955–56 37 41
   Google Scholar
• Reinhard Diestel, Graph Theory, third ed., Grad. Texts in Math, vol. 173, Springer, Berlin, 2006.
   Google Scholar
• W.T. Tutte, Graph Theory, Encyc. Math. Appl, vol. 21, Addison-Wesley, Reading, Mass, 1984. Repr. Cambridge Univ. Press, Cambridge, Eng., 2001.
   Google Scholar
• Truemper Klaus Alpha-balanced graphs and matrices and GF(3)-representability of matroids J. Combin. Theory Ser. B 32 1982 112 139
   Web of Science ®Google Scholar
• Slilaty Daniel C. Projective-planar signed graphs and tangled signed graphs J. Combin. Theory Ser. B 97 5 2007 693 717
   Web of Science ®Google Scholar
• Thomas Zaslavsky, Quasibalanced signed graphs, in preparation.
   Google Scholar
• Vušković Kristina Even-hole-free graphs: a survey Appl. Anal. Discrete Math. 4 2 2010 219 240
   Google Scholar
• Conforti Michele Cornuéjols Gérard Kapoor Ajai Vuškoviić Kristina Even and odd holes in cap-free graphs J. Graph Theory 30 1999 289 308
   Web of Science ®Google Scholar
• Hochstättler Winfried Nickel Robert Peis Britta Two disjoint negative cycles in a signed graph Electron. Notes Discrete Math. 50 2006 107 111
   Google Scholar
• Zaslavsky Thomas Signed graphs Discrete Appl. Math. 4 1982 47 74 Discrete Appl. Math. 5 1983 248 (erratum)
   Web of Science ®Google Scholar
• Ouahiba Bessouf, Abdelkader Khelladi, Thomas Zaslavsky, New concept of connection in signed graphs, submitted for publication.
   Google Scholar
• Cai Leishen Schieber Baruch A linear-time algorithm for computing the intersection of all odd cycles in a graph Discrete Appl. Math. 73 1997 27 34
   Web of Science ®Google Scholar
• Conforti Michele Gerards Bert Packing odd circuits SIAM J. Discrete Math. 21 2 2007 273 302
   Web of Science ®Google Scholar
• Geelen James F. Guenin Bertrand Packing odd circuits in eulerian graphs J. Combin. Theory Ser. B 86 2 2002 280 295
   Web of Science ®Google Scholar
• Král’ Daniel Sereni Jean-Sébastien Stacho Ladislav Min–max relations for odd cycles in planar graphs SIAM J. Discrete Math. 26 3 2012 884 895
   Web of Science ®Google Scholar
• Thomassen Carsten The Erdős–Pósa property for odd cycles in graphs of large connectivity Combinatorica 21 2 2001 321 333
   Web of Science ®Google Scholar
• Rautenbach Dieter Reed Bruce The Erdős–Pósa property for odd cycles in highly connected graphs Combinatorica 21 2001 267 278
   Web of Science ®Google Scholar
• Berge Claude Reed Bruce Optimal packings of edge-disjoint odd cycles Discrete Math. 211 2000 197 202
   Web of Science ®Google Scholar
• Chiba Shuya Fujita Shinya Kawarabayashi Ken-ichi Sakuma Tadashi Minimum degree conditions for vertex-disjoint even cycles in large graphs Adv. Appl. Math. 54 2014 105 120
   Web of Science ®Google Scholar
• Golovach Petr A. Kamiński Marcin Paulusma Daniël Thilikos Dimitrios M. Induced packing of odd cycles in planar graphs Theoret. Comput. Sci. 420 2012 28 35
   Web of Science ®Google Scholar
• Král’ Daniel Voss Heinz-Jürgen Edge-disjoint odd cycles in planar graphs J. Combin. Theory Ser. B 90 2004 107 120
   Web of Science ®Google Scholar
• Tomás Feder, Carlos Subi, Packing Edge-disjoint triangles in given graphs, Electronic Colloquium on Computational Complexity, Report No. TR12-013, 2012, 12 pp.
   Google Scholar
• Huynh Tony Oum Sang-il Verdian-Rizi Maryam Even cycle decompositions of graphs with no odd-K4-minor European J. Combin. 65 2017 1 14
   Web of Science ®Google Scholar
• Máčajová Edita Mazák Ján On even cycle decompositions of 4-regular line graphs Discrete Math. 313 2013 1697 1699
   Web of Science ®Google Scholar
• Huynh Tony King Andrew D. Oum Sang-Il Verdian-Rizi Maryam Strongly even cycle decomposable graphs J. Graph Theory 84 2 2017 158 175
   Web of Science ®Google Scholar
• Huck Andreas Kochol Martin Five cycle double covers of some cubic graphs J. Combin. Theory Ser. B 64 1995 119 125
   Web of Science ®Google Scholar
• Popescu Dragoş Proprietati ale grafurilor semnate [Properties of signed graphs] (in Romanian; French summary) Stud. Cerc. Mat. 31 1979 433 452
   Google Scholar
• Conlon Joseph G. Even cycles in graphs J. Graph Theory 45 3 2004 163 223
   Web of Science ®Google Scholar
• Fujita Shinya Kawarabayashi Ken-Ichi Non-separating even cycles in highly connected graphs Combinatorica 30 5 2010 565 580
   Web of Science ®Google Scholar
• Voss Heinz-Jürgen Cycles and Bridges in Graphs 1991 Kluwer, Dordrecht, and Deutscher Verlag der Wissenschaften Berlin
   Google Scholar
• Kittipassorn Teeradej Mészáros Gábor Frustrated triangles Discrete Math. 338 12 2015 2363 2373
   Web of Science ®Google Scholar
• Popescu Dragoş-Radu Tomescu Ioan Negative cycles in complete signed graphs Discrete Appl. Math. 68 1996 145 152
   Web of Science ®Google Scholar
• Alex Schaefer, Thomas Zaslavsky, The dimension of the negative cycle vectors of signed complete graphs, submitted for publication.
   Google Scholar
• Popescu Dragoş-Radu Une méthode d’énumération des cycles négatifs d’un graphe signé Discrete Math. 150 1996 337 345
   Google Scholar
• Cvetković Dragoš M. Signless Laplacians and line graphs Bull. Cl. Sci. Math. Nat. Sci. Math. 30 2005 86 92
   Google Scholar
• Hou Yaoping Li Jiongsheng Pan Yongliang On the Laplacian eigenvalues of signed graphs Linear Multilinear Algebra 51 2003 21 30
   Web of Science ®Google Scholar
• Reff Nathan Spectral properties of complex unit gain graphs Linear Algebra Appl. 436 9 2012 3165 3176
   Web of Science ®Google Scholar
• Nikiforov Vladimir A spectral condition for odd cycles in graphs Linear Algebra Appl. 428 7 2008 1492 1498
   Web of Science ®Google Scholar
• Yuan Xiying Maxima of the Q-index: forbidden odd cycles Linear Algebra Appl. 458 2014 207 216 Linear Algebra Appl. 65 2015 426 429 (corrigendum)
   Web of Science ®Google Scholar
• Nikiforov Vladimir Yuan Xiying Maxima of the Q-index: forbidden even cycles Linear Algebra Appl. 471 2015 636 653
   Web of Science ®Google Scholar
• Harary Frank Norman Robert Z. Cartwright Dorwin Structural Models: An Introduction to the Theory of Directed Graphs 1965 Wiley New York
   Google Scholar
• Harary Frank Richard Lundgren J. Maybee John S. On signed digraphs with all cycles negative Discrete Appl. Math. 12 1985 155 164
   Web of Science ®Google Scholar
• Chaty Guy On signed digraphs with all cycles negative Discrete Appl. Math. 20 1988 83 85
   Web of Science ®Google Scholar
• Montalva Marco Aracena Julio Gajardo Anahí On the complexity of feedback set problems in signed digraphs IV Latin-American Algorithms, Graphs, and Optimization Sympos. (Puerto Varas, Chile, 2007) Electron. Notes Discrete Math. 30 2008 249 254
   Google Scholar