Wyniki wyszukiwania - BazTech

1

Subgroup Switching of Skew Gain Graphs

Hage J.

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

111-122

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.

2

The Embedding Problem for Switching Classes of Graphs

Ehrenfeucht A., Hage J., Harju T., Rozenberg G.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 1

115-134

EN

In the context of graph transformation we look at the operation of switching, which can be viewed as a method for realizing global transformations of (group-labelled) graphs through local transformations of the vertices. In case vertices are given an identity, various relatively efficient algorithms exist for deciding whether a graph can be switched so that it contains some other graph, the query graph, as an induced subgraph. However, when considering graphs up to isomorphism, we immediately run into the graph isomorphism problem for which no efficient solution is known. Surprisingly enough however, in some cases the decision process can be simplified by transforming the query graph into a ``smaller'' graph without changing the answer. The main lesson learned is that the size of the query graph is not the dominating factor, but its cycle rank. Although a number of our results hold specifically for undirected, unlabelled graphs, we propose a more general framework and give many positive and negative results for more general cases, where the graphs are labelled with elements of a (finitely generated abelian) group.

3

Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

Hage J., Harju T., Welzl E.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 1

23--37

EN

In the context of graph transformations we look at the operation of switching, which can be viewed as a method for realizing global transformations of graphs through local transformations of the vertices. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation. Continuing the line of research in Ehrenfeucht, Hage, Harju and Rozenberg we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.