An algorithm for road coloring

A coloring of edges of a finite directed graph turns the graph into a finite-state automaton. A synchronizing word of a deterministic automaton is a word in the alphabet of colors of its edges (regarded as letters) which maps the automaton to a single state. A coloring of edges of a directed graph of uniform outdegree (constant outdegree of any vertex) is synchronizing if the corresponding deterministic finite automaton possesses a synchronizing word.The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph of uniform outdegree if the greatest common divisor of lengths of all its cycles is one. Posed in 1970, it has evoked noticeable interest among the specialists in the theory of graphs, automata, codes, symbolic dynamics, and well beyond these areas.We present an algorithm for the road coloring of cubic worst-case time complexity and quadratic time complexity in the majority of studied cases. It is based on the recent positive solution of the road coloring problem. The algorithm was implemented in the freeware package TESTAS.     

A PTAS for minimum <Emphasis Type="Italic">d</Emphasis>-hop connected dominating set in growth-bounded graphs

In this paper, we design the first polynomial time approximation scheme for d-hop connected dominating set (d-CDS) problem in growth-bounded graphs, which is a general type of graphs including unit disk graph, unit ball graph, etc. Such graphs can represent majority types of existing wireless networks. Our algorithm does not need geometric representation (e.g., specifying the positions of each node in the plane) beforehand. The main strategy is clustering partition. We select the d-CDS for each subset separately, union them together, and then connect the induced graph of this set. We also provide detailed performance and complexity analysis.     

Surviving rate of graphs and Firefighter Problem

The Firefighter Problem on a graph can be viewed as a simplified model of the spread of contagion, fire, rumor, computer virus, etc. The fire breaks out at one or more vertices in a graph at the first round, and the fire-fighter chooses some vertices to protect. The fire spreads to all non-protected neighbors at the beginning of each time-step. The process stops when the fire can no longer spread. The Firefighter Problem has attracted considerable attention since it was introduced in 1995. In this paper we provide a survey on recent research progress of this field, including algorithms and complexity, Fire-fighter Problem for special graphs (finite and infinite) and digraphs, surviving rate and burning number of graphs. We also collect some open problems and possible research subjects.     

图的存活率与消防员问题

消防员问题可视为传染病、火灾、谣言、计算机病毒等传播的一个简化模型.假设一把火在一个图的某个点或多个点燃起,消防员选择若干个未着火的顶点进行防护,然后火蔓延到前一步着火点的未燃邻点.当火不再蔓延时整个过程结束.消防员问题自1995年提出以来引起了人们的广泛关注.本文简述了与消防员问题相关的最近研究进展,包括算法复杂性、无限图和有向图的消防员问题、图的存活率、图的燃烧数及一些有待于进一步研究的问题.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

DNA recombination through assembly graphs

Motivated by DNA rearrangements and DNA homologous recombination modeled in [A. Angeleska, N. Jonoska, M. Saito, L.F. Landweber, RNA-guided DNA assembly, Journal of Theoretical Biology, 248(4) (2007), 706–720], we investigate smoothings on graphs that consist of only 4-valent and 1-valent rigid vertices, called assembly graphs. An assembly graph can be seen as a representation of the DNA during certain recombination processes in which 4-valent vertices correspond to the alignment of the recombination sites. A single gene is modeled by a polygonal path in an assembly graph. A polygonal path makes a “right-angle” turn at every vertex, defining smoothings at the 4-valent vertices and therefore modeling the recombination process. We investigate the minimal number of polygonal paths visiting all vertices of a given graph exactly once, and show that for every positive integer n there are graphs that require at least n such polygonal paths. We show that there is an embedding in three-dimensional space of each assembly graph such that smoothing of vertices according to a given set of polygonal paths results in an unlinked graph. As some recombination processes may happen simultaneously, we characterize the subsets of vertices whose simultaneous smoothings keep a given gene in tact and give a characterization of all sequences of sets of vertices defining successive simultaneous smoothings that can realize complete gene rearrangement.     

Complexity of networks I: The set‐complexity of binary graphs

The balance between symmetry and randomness as a property of networks can be viewed as a kind of “complexity.” We use here our previously defined “set complexity” measure (Galas et al., IEEE Trans Inf Theory 2010, 56), which was used to approach the problem of defining biological information, in the mathematical analysis of networks. This information theoretic measure is used to explore the complexity of binary, undirected graphs. The complexities, Ψ, of some specific classes of graphs can be calculated in closed form. Some simple graphs have a complexity value of zero, but graphs with significant values of Ψ are rare. We find that the most complex of the simple graphs are the complete bipartite graphs (CBGs). In this simple case, the complexity, Ψ, is a strong function of the size of the two node sets in these graphs. We find the maximum Ψ binary graphs as well. These graphs are distinct from, but similar to CBGs. Finally, we explore directed and stochastic processes for growing graphs (hill‐climbing and random duplication, respectively) and find that node duplication and partial node duplication conserve interesting graph properties. Partial duplication can grow extremely complex graphs, while full node duplication cannot do so. By examining the eigenvalue spectrum of the graph Laplacian we characterize the symmetry of the graphs and demonstrate that, in general, breaking specific symmetries of the binary graphs increases the set‐based complexity, Ψ. The implications of these results for more complex, multiparameter graphs, and for physical and biological networks and the processes of network evolution are discussed. © 2011 Wiley Periodicals, Inc. Complexity, 17,51–64, 2011     

Černý’s conjecture and group representation theory

Let us say that a Cayley graph Γ of a group G of order n is a Černy Cayley graph if every synchronizing automaton containing Γ as a subgraph with the same vertex set admits a synchronizing word of length at most (n−1)². In this paper we use the representation theory of groups over the rational numbers to obtain a number of new infinite families of Černy Cayley graphs.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

A classification of tightly attached half-arc-transitive graphs of valency 4

A graph is said to be half-arc-transitive if its automorphism group acts transitively on the set of its vertices and edges but not on the set of its arcs. With each half-arc-transitive graph of valency 4 a collection of the so-called alternating cycles is associated, all of which have the same even length. Half of this length is called the radius of the graph in question. Moreover, any two adjacent alternating cycles have the same number of common vertices. If this number, the so-called attachment number, coincides with the radius, we say that the graph is tightly attached. In [D. Marušič, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B 73 (1998) 41–76], Marušič gave a classification of tightly attached half-arc-transitive graphs of valency 4 with odd radius. In this paper the even radius tightly attached graphs of valency 4 are classified, thus completing the classification of all tightly attached half-arc-transitive graphs of valency 4.