Subgroup Switching of Skew Gain Graphs

• Autorzy: Hage J.
• Języki publikacji: EN

Abstrakty

EN

Gain graphs are graphs in which each edge has a gain (a label from a group so that reversing the direction of an edge inverts the gain). In this paper we take a generalized view of gain graphs in which the gain of an edge is related to the gain of the reverse edge by an anti-involution, i.e., an anti-automorphism of order at most two. We call these skew gain graphs. Switching is an operation that transforms one skew gain graph into another, driven by a selector that selects an element of some group Γ in each of its vertices. In this paper, we investigate a generalization of this model, in which we insist that in each vertex v the selected elements are taken from a subgroup Γ_v of Γ. We call this operation subgroup switching. Our main interest in this paper is in establishing which properties of the theory of switching classes of the skew gain graphs carry over to subgroup switching classes, and which do not.

Słowa kluczowe

EN

gain graphs; switching

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 111--122
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Hage J.

• Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands,

Bibliografia

• [1] H. Bodlaender and J. Hage. On switching classes, NLC-width, cliquewidth and treewidth. Theoretical Computer Science. Accepted for publication.
• [2] C. J. Colbourn and D. G. Corneil. On deciding switching equivalence of graphs. Discrete Math., 2:181 - 184, 1980.
• [3] A. Ehrenfeucht, J. Hage, T. Harju, and G. Rozenberg. Complexity issues in switching of graphs. In H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, editors, Theory And Application Of Graph Transformations - TAGT '98, volume 1764 of Lecture Notes in Computer Science, pages 59-70, Berlin, 2000. Springer Verlag.
• [4] A. Ehrenfeucht, J. Hage, T. Harju, and G. Rozenberg. Pancyclicity in switching classes. Inf. Proc. Letters, 73(5-6):153 - 156, 2000.
• [5] A. Ehrenfeucht, T. Harju, and G. Rozenberg. The Theory of 2-Structures. World Scientific, Singapore, 1999.
• [6] A. Ehrenfeucht and G. Rozenberg. Dynamic labeled 2-structures. Mathematical Structures in Computer Science, 4:433-455, 1994.
• [7] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.
• [8] J. L. Gross and T. W. Tucker. Topological Graph Theory. Wiley, New York, 1987.
• [9] J. Hage. The membership problem for switching classes with skew gains. Fundamenta Informaticae, 39(4):375-387, 1999.
• [10] J. Hage. Structural Aspects Of Switching Classes. PhD thesis, Leiden Institute of Advanced Computer Science, 2001. http://www.cs.uu.nl/people/jur/2s.html.
• [11] J. Hage and T. Harju. Acyclicity of switching classes. European J. Combin., 19:321-327, 1998.
• [12] J. Hage and T. Harju. The size of switching classes with skew gains. Discrete Math., 215:81 - 92, 2000.
• [13] J. Hage and T. Harju. A characterization of acyclic switching classes using forbidden subgraphs. SIAM Journal on Discrete Mathematics, 18(1):159 - 176, 2004.
• [14] J. Hage, T. Harju, and E. Welzl. Euler graphs, triangle-free graphs and bipartite graphs in switching classes. Fundamenta Informaticae, 58(1):23-37, November 2003.
• [15] F. Harary. On the notion of balance of a signed graph. Michigan Math. J., 2:143-146, 1953-1954. Addendum in same journal preceding page 1.
• [16] A. Hertz. On perfect switching classes. Discrete Applied Math., 89:263-267, 1998.
• [17] J. J. Seidel. Graphs and two-graphs. In Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Winnipeg, Canada, 1974. Utilitas Mathematica Publishing Inc.
• [18] T. Zaslavsky. Characterizations of signed graphs. J. Graph Theory, 5:401-406, 1981.
• [19] T. Zaslavsky. Signed graphs. Discrete Applied Math., 4:47-74, 1982. Erratum on p. 248 of volume 5.
• [20] T. Zaslavsky. Biased graphs. I. Bias, balance, and gains. J. Combin. Theory, Ser. B, 47:32-52, 1989.
• [21] T. Zaslavsky. A mathematical bibliography of signed and gain graphs and allied areas. Electronic J. Combin., 1999. Dynamic Survey No. DS8.