Vol. 17 no. 1


1. A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon

Cabello, Sergio ; Saumell, Maria.
We present a randomized algorithm to compute a clique of maximum size in the visibility graph G of the vertices of a simple polygon P. The input of the problem consists of the visibility graph G, a Hamiltonian cycle describing the boundary of P, and a parameter δ∈(0,1) controlling the probability of […]
Section: Discrete Algorithms

2. Ore-degree threshold for the square of a Hamiltonian cycle

DeBiasio, Louis ; Faizullah, Safi ; Khan, Imdadullah.
A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n=2 contains a Hamiltonian cycle. In 1963, P´osa conjectured that every graph with minimum degree at least 2n=3 contains the square of a Hamiltonian cycle. In 1960, Ore relaxed the degree condition in the […]
Section: Graph Theory

3. An approximability-related parameter on graphs―-properties and applications

Engström, Robert ; Färnqvist, Tommy ; Jonsson, Peter ; Thapper, Johan.
We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results […]
Section: Graph Theory

4. On the 1-2-3-conjecture

Davoodi, Akbar ; Omoomi, Behnaz.
A k-edge-weighting of a graph G is a function w:E(G)→{1,…,k}. An edge-weighting naturally induces a vertex coloring c, where for every vertex v∈V(G), c(v)=∑e∼vw(e). If the induced coloring c is a proper vertex coloring, then w is called a vertex-coloring k-edge-weighting (VC k-EW). Karoński et al. […]
Section: Graph Theory

5. Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes

Azarija, Jernej ; Klavžar, Sandi ; Lee, Jaehun ; Rho, Yoomi.
If f is a binary word and d a positive integer, then the generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all the vertices that contain f as a factor, while the generalized Lucas cube Qd(lucas(f)) is the graph obtained from Qd by removing all the vertices that […]
Section: Graph Theory

6. Classification of skew translation generalized quadrangles, I

Thas, Koen.
We describe new classification results in the theory of generalized quadrangles (= Tits-buildings of rank 2 and type B2), more precisely in the (large) subtheory of skew translation generalized quadrangles (``STGQs''). Some of these involve, and solve, long-standing open problems.
Section: Combinatorics

7. Symmetric bipartite graphs and graphs with loops

Cairns, Grant ; Mendan, Stacey.
We show that if the two parts of a finite bipartite graph have the same degree sequence, then there is a bipartite graph, with the same degree sequences, which is symmetric, in that it has an involutive graph automorphism that interchanges its two parts. To prove this, we study the relationship […]
Section: Graph Theory

8. Edge stability in secure graph domination

Burger, Anton Pierre ; Villiers, Alewyn Petrus,  ; Vuuren, Jan Harm, .
A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X-v)∪u is again a dominating set of G. The secure domination number of G is the cardinality […]
Section: Graph Theory

9. Bootstrapping and double-exponential limit laws

Prodinger, Helmut ; Wagner, Stephan.
We provide a rather general asymptotic scheme for combinatorial parameters that asymptotically follow a discrete double-exponential distribution. It is based on analysing generating functions Gh(z) whose dominant singularities converge to a certain value at an exponential rate. This behaviour is […]
Section: Combinatorics

10. Avoider-enforcer star games

Grzesik, Andrzej ; Mikalački, Mirjana ; Nagy, Zoltán Lóránt ; Naor, Alon ; Patkós, Balázs ; Skerman, Fiona.
In this paper, we study (1 : b) Avoider-Enforcer games played on the edge set of the complete graph on n vertices. For every constant k≥3 we analyse the k-star game, where Avoider tries to avoid claiming k edges incident to the same vertex. We consider both versions of Avoider-Enforcer games — the […]
Section: Combinatorics

11. p-box: a new graph model

Soto, Mauricio ; Thraves-Caro, Christopher.
In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our […]
Section: Graph Theory

12. Guarded subgraphs and the domination game

Brešar, Boštjan ; Klavžar, Sandi ; Košmrlj, Gasper ; Rall, Doug F..
We introduce the concept of guarded subgraph of a graph, which as a condition lies between convex and 2-isometric subgraphs and is not comparable to isometric subgraphs. Some basic metric properties of guarded subgraphs are obtained, and then this concept is applied to the domination game. In this […]
Section: Graph Theory

13. Extending a perfect matching to a Hamiltonian cycle

Alahmadi, Adel ; Aldred, Robert E. L. ; Alkenani, Ahmad ; Hijazi, Rola ; Solé, P. ; Thomassen, Carsten.
Ruskey and Savage conjectured that in the d-dimensional hypercube, every matching M can be extended to a Hamiltonian cycle. Fink verified this for every perfect matching M, remarkably even if M contains external edges. We prove that this property also holds for sparse spanning regular subgraphs of […]
Section: Graph Theory

14. A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs

Bodroža-Pantić, Olga ; Kwong, Harris ; Pantić, Milan.
We study the enumeration of Hamiltonian cycles on the thin grid cylinder graph $C_m \times P_{n+1}$. We distinguish two types of Hamiltonian cycles, and denote their numbers $h_m^A(n)$ and $h_m^B(n)$. For fixed $m$, both of them satisfy linear homogeneous recurrence relations with constant […]
Section: Graph Theory

15. Cost-effectiveness of algorithms

Farr, Graham.
In this paper we discuss how to assess the performance of algorithms for optimisation problems in a way that balances solution quality and time. We propose measures of cost-effectiveness for such algorithms. These measures give the gain in solution quality per time unit over a sequence of inputs, […]
Section: Discrete Algorithms

16. On probe 2-clique graphs and probe diamond-free graphs

Bonomo, Flavia ; Figueiredo, Celina M. H.,  ; Duran, Guillermo ; Grippo, Luciano N. ; Safe, Martín D. ; Szwarcfiter, Jayme L..
Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the […]
Section: Graph Theory

17. Parameterized complexity of synchronization and road coloring

Vorel, Vojtěch ; Roman, Adam.
First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we […]
Section: Automata, Logic and Semantics

18. Graphs with large disjunctive total domination number

Henning, Michael A. ; Naicker, Viroshan.
Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a […]
Section: Graph Theory

19. A note on a recent attempt to improve the Pin-Frankl bound

Gonze, François ; Jungers, Raphaël M. ; Trahtman, Avraham N..
We provide a counterexample to a lemma used in a recent tentative improvement of the Pin-Frankl bound for synchronizing automata. This example naturally leads us to formulate an open question, whose answer could fix the line of the proof, and improve the bound.
Section: Automata, Logic and Semantics

20. Output sensitive algorithms for covering many points

Ghasemalizadeh, Hossein ; Razzazi, Mohammadreza.
In this paper we devise some output sensitive algorithms for a problem where a set of points and a positive integer, m, are given and the goal is to cover a maximal number of these points with m disks. We introduce a parameter, ρ, as the maximum number of points that one disk can cover and we […]
Section: Discrete Algorithms

21. An efficient certificateless aggregate signature scheme for vehicular ad-hoc networks

Malhi, Avleen Kaur ; Batra, Shalini.
The state-of-the-art telecommunication technologies have widely been adapted for sensing the traffic related information and collection of it. Vehicular Ad-Hoc Networks (VANETs) have emerged as a novel technology for revolutionizing the driving experiences of human. The most effective and widely […]
Section: Distributed Computing and Networking

22. Maximum difference about the size of optimal identifying codes in graphs differing by one vertex

Pelto, Mikko.
Let G=(V,E) be a simple undirected graph. We call any subset C⊆V an identifying code if the sets I(v)={c∈C | {v,c}∈E or v=c } are distinct and non-empty for all vertices v∈V. A graph is called twin-free if there is an identifying code in the graph. The identifying code with minimum size in a […]
Section: Graph Theory

23. On the Hausdorff measure of regular ω-languages in Cantor space

Staiger, Ludwig.
This paper deals with the calculation of the Hausdorff measure of regular ω-languages, that is, subsets of the Cantor space definable by finite automata. Using methods for decomposing regular ω-languages into disjoint unions of parts of simple structure we derive two sufficient conditions under […]
Section: Automata, Logic and Semantics

24. Snarks with total chromatic number 5

Brinkmann, Gunnar ; Preissmann, Myriam ; Sasaki, Diana.
A k-total-coloring of G is an assignment of k colors to the edges and vertices of G, so that adjacent and incident elements have different colors. The total chromatic number of G, denoted by χT(G), is the least k for which G has a k-total-coloring. It was proved by Rosenfeld that the total chromatic […]
Section: Graph Theory

25. On substitution tilings of the plane with n-fold rotational symmetry

Maloney, Gregory R..
A method is described for constructing, with computer assistance, planar substitution tilings that have n-fold rotational symmetry. This method uses as prototiles the set of rhombs with angles that are integer multiples of pi/n, and includes various special cases that have already been constructed […]
Section: Discrete Algorithms

26. Intervals and factors in the Bruhat order

Tenner, Bridget Eileen.
In this paper we study those generic intervals in the Bruhat order of the symmetric group that are isomorphic to the principal order ideal of a permutation w, and consider when the minimum and maximum elements of those intervals are related by a certain property of their reduced words. We show that […]
Section: Combinatorics

27. How often should you clean your room?

Martin, Kimball ; Shankar, Krishnan.
We introduce and study a combinatorial optimization problem motivated by the question in the title. In the simple case where you use all objects in your room equally often, we investigate asymptotics of the optimal time to clean up in terms of the number of objects in your room. In particular, we […]
Section: Analysis of Algorithms