Vol. 14 no. 2


1. On bipartite powers of bigraphs

Okamoto, Yoshio ; Otachi, Yota ; Uehara, Ryuhei.
The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under […]
Section: Graph Theory

2. The competition number of a generalized line graph is at most two

Park, Boram ; Sano, Yoshio.
In 1982, Opsut showed that the competition number of a line graph is at most two and gave a necessary and sufficient condition for the competition number of a line graph being one. In this paper, we generalize this result to the competition numbers of generalized line graphs, that is, we show that […]
Section: Graph Theory

3. Random Horn formulas and propagation connectivity for directed hypergraphs

Sloan, Robert H. ; Stasi, Despina ; Turán, György.
We consider the property that in a random definite Horn formula of size-3 clauses over n variables, where every such clause is included with probability p, there is a pair of variables for which forward chaining produces all other variables. We show that with high probability the property does not […]
Section: Combinatorics

4. On neighbour-distinguishing colourings from lists

Horňák, Mirko ; WoźniaK, Mariusz.
An edge colouring of a graph is said to be neighbour-distinguishing if any two adjacent vertices have distinct sets of colours of their incident edges. In this paper the list version of the problem of determining the minimum number of colours in a neighbour-distinguishing colouring of a given graph […]
Section: Graph and Algorithms

5. Some results on stable sets for k-colorable P₆-free graphs and generalizations

Mosca, Raffaele.
This article deals with the Maximum Weight Stable Set (MWS) problem (and some other related NP-hard problems) and the class of P-6-free graphs. The complexity status of MWS is open for P-6-free graphs and is open even for P-5-free graphs (as a long standing open problem). Several results are known […]
Section: Graph and Algorithms

6. On paths, trails and closed trails in edge-colored graphs

Gourvès, Laurent ; Lyra, Adria ; Martinhon, Carlos A. ; Monnot, Jérôme.
In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G(c), we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex […]
Section: Graph Theory

7. Graphs with many vertex-disjoint cycles

Rautenbach, Dieter ; Regen, Friedrich.
We study graphs G in which the maximum number of vertex-disjoint cycles nu(G) is close to the cyclomatic number mu(G), which is a natural upper bound for nu(G). Our main result is the existence of a finite set P(k) of graphs for all k is an element of N-0 such that every 2-connected graph G with […]
Section: Graph Theory

8. Random Cayley digraphs of diameter 2 and given degree

Lladser, Manuel E. ; Potočnik, Primož ; Širáň, Jozef ; Wilson, Mark C..
We consider random Cayley digraphs of order n with uniformly distributed generating sets of size k. Specifically, we are interested in the asymptotics of the probability that such a Cayley digraph has diameter two as n -> infinity and k = f(n), focusing on the functions f(n) = left […]
Section: Graph Theory

9. The asymmetric leader election algorithm with Swedish stopping: a probabilistic analysis

Louchard, Guy ; Prodinger, Helmut.
We study a leader election protocol that we call the Swedish leader election protocol. This name comes from a protocol presented by L. Bondesson, T. Nilsson, and G. Wikstrand (2007). The goal is to select one among n > 0 players, by proceeding through a number of rounds. If there is only one […]
Section: Analysis of Algorithms

10. The analysis of find and versions of it

Knof, Diether ; Roesler, Uwe.
In the running time analysis of the algorithm Find and versions of it appear as limiting distributions solutions of stochastic fixed points equation of the form X D = Sigma(i) AiXi o Bi + C on the space D of cadlag functions. The distribution of the D-valued process X is invariant by some random […]
Section: Analysis of Algorithms

11. Acyclic chromatic index of fully subdivided graphs and Halin graphs

Basavaraju, Manu.
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph G is called fully subdivided if it is […]
Section: Graph Theory

12. Immersion containment and connectivity in color-critical graphs

Abu-Khzam, Faisal N. ; Langston, Michael A..
The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. It is shown that a t-chromatic graph G contains either an immersed Kt or an immersed t-chromatic subgraph that is both 4-vertex-connected and […]
Section: Graph Theory

13. On 4-valent Frobenius circulant graphs

Zhou, Sanming.
A 4-valent first-kind Frobenius circulant graph is a connected Cayley graph DLn(1, h) = Cay(Zn, H) on the additive group of integers modulo n, where each prime factor of n is congruent to 1 modulo 4 and H = {[1], [h], −[1], −[h]} with h a solution to the congruence equation x 2 + 1 ≡ 0 (mod n). In […]
Section: Graph Theory

14. Digraph complexity measures and applications in formal language theory

Gruber, Hermann.
We investigate structural complexity measures on digraphs, in particular the cycle rank. This concept is intimately related to a classical topic in formal language theory, namely the star height of regular languages. We explore this connection, and obtain several new algorithmic insights regarding […]
Section: Automata, Logic and Semantics

15. A note on planar Ramsey numbers for a triangle versus wheels

Zhou, Guofei ; Chen, Yaojun ; Miao, Zhengke ; Pirzada, Shariefuddin.
For two given graphs G and H , the planar Ramsey number P R ( G; H ) is the smallest integer n such that every planar graph F on n vertices either contains a copy of G , or its complement contains a copy of H . In this paper, we determine all planar Ramsey numbers for a triangle versus wheels.
Section: Graph Theory

16. Random graphs with bounded maximum degree: asymptotic structure and a logical limit law

Koponen, Vera.
For any fixed integer R≥2 we characterise the typical structure of undirected graphs with vertices 1,...,n and maximum degree R, as n tends to infinity. The information is used to prove that such graphs satisfy a labelled limit law for first-order logic. If R≥5 then also an unlabelled limit law […]

17. On quadratic threshold CSPs

Austrin, Per ; Benabbas, Siavosh ; Magen, Avner.
A predicate P: {-1, 1}k →{0, 1} can be associated with a constraint satisfaction problem Max CSP(P). P is called ''approximation resistant'' if Max CSP(P) cannot be approximated better than the approximation obtained by choosing a random assignment, and ''approximable'' otherwise. This […]
Section: Discrete Algorithms

18. On the algebraic numbers computable by some generalized Ehrenfest urns

Albenque, Marie ; Gerin, Lucas.
This article deals with some stochastic population protocols, motivated by theoretical aspects of distributed computing. We modelize the problem by a large urn of black and white balls from which at every time unit a fixed number of balls are drawn and their colors are changed according to the […]

19. Secure frameproof codes through biclique covers

Hajiabolhassan, Hossein ; Moazami, Farokhlagha.
For a binary code Γ of length v, a v-word w produces by a set of codewords {w1,...,wr}⊆Γ if for all i=1,...,v, we have wi∈{w1i,...,wri} . We call a code r-secure frameproof of size t if |Γ|=t and for any v-word that is produced by two sets C1 and C2 of size at most r then the intersection of these […]
Section: Graph Theory

20. Upper k-tuple domination in graphs

Chang, Gerard Jennhwa ; Dorbec, Paul ; Kim, Hye Kyung ; Raspaud, André ; Wang, Haichao ; Zhao, Weiliang.
For a positive integer k, a k-tuple dominating set of a graph G is a subset S of V (G) such that |N [v] ∩ S| ≥ k for every vertex v, where N [v] = {v} ∪ {u ∈ V (G) : uv ∈ E(G)}. The upper k-tuple domination number of G, denoted by Γ×k (G), is the maximum cardinality of a minimal k-tuple dominating […]
Section: Graph Theory