Volume 44 – 2016 – 6th Latin-American Workshop on Cliques in Graphs

Articles

6th Latin-American Workshop on Cliques in Graphs – Prefácio

Autores:Celina M. H. de Figueiredo, Claudson Bornstein, Erika M. M. Coelho, Márcia R. Cappelle

Download

Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets

The Cluster Editing problem aims to transform an undirected graph into a vertex-disjoint union of cliques by adding or deleting at most k edges. It has been proven NP-hard several times as it has been discovered and rediscovered in important application areas. Most biologists, social scientists and other practitioners have databases and networks that need clustering.
Autor:Frances A. Rosamond

Download

The Burning of the Snark

The firefighter game is a model of the containment of the spreading of an undesired property within a network, like an infecting dis-
ease. In 2007, Finbow et al. showed that finding an optimal strategy is NP-hard for trees of maximum degree three, and presented a tractable case on graphs of maximum degree three when the fire breaks out at a vertex of degree two.
Autores:Vitor Costa, Simone Dantas, Dieter Rautenbach

Download

Total coloring of snarks is NP-complete

Snarks are bridgeless cubic graphs that do not allow 3-edgecolorings. We prove that the problem of determining if a snark is of Type 1 is NP-complete.
Autores:Vinícius F. dos Santos, Diana Sasaki

Download

On local edge intersection graphs of paths on bounded degree trees

An undirected graph G is called an EPT graph if it is the edge intersection graph of a family of paths in a tree. We call G a local
EPT graph if it is the EPT graph of a collection of paths P which all share a common vertex. In this paper, we characterize the local EPT graphs which can be represented in a host tree with maximum degree h.
Autores:Liliana Alcón Marisa Gutierrez, Marisa Pía Mazzoleni

Download

The k-in-a-tree problem for chordal graphs

Algorithms for detecting particular induced subgraphs have been the focus of much research recently, mostly related to their connection
to many classes of graphs defined by forbidden induced subgraphs. In this context, Chudnovsky and Seymour proposed a useful tool, called three-in-a-tree algorithm which solves the following problem in polynomial time: given a graph with three prescribed vertices, test if there is an induced tree containing these vertices.
Autores:Vinícius F. dos Santos Murilo V. G. da Silva, Jayme L. Szwarcfiter

Download

Sorting Separable Permutations by Restricted Multi-break Rearrangements

A multi-break rearrangement generalizes most of genome rearrangements, such as block-interchanges, transpositions and reversals. A k-break cuts k adjacencies over a permutation, and forms k new adjacencies by joining the extremities according to an arbitrary matching. Block-interchange distance is a polynomial problem, but the transposition and the reversal distances are both NP-hard problems.
Autores:Luís Felipe I. Cunha, Luis Antonio B. Kowada, Celina M. H. de Figueiredo

Download

Timber Game with Caterpillars

Timber is a two player game played on a directed graph, with a domino on each arc. The direction of the arc indicates the direc-
tion in which the domino can be initially toppled. If one domino is toppled, it topples the dominoes in the direction it was toppled and creates a chain reaction. The goal of this game is to topple all the dominoes and the player who topples the last dominoes wins.
Autores:Ana Furtado, Simone Dantas, Celina de Figueiredo, Sylvain Gravier

Download

The AVD-edge-coloring conjecture for some split graphs

Let G be a simple graph. An adjacent vertex distinguishing edgecoloring (AVD-edge-coloring) of G is an edge-coloring of G such that for each pair of adjacent vertices u; v of G, the set of colors assigned to the edges incident with u differs from the set of colors assigned to the edges incident with v.
Autores:Aloísio de Menezes Vilas-Bôas, Célia Picinin de Mello

Download

Maximum Clique via MaxSat and Back Again

Branch and bound algorithms stand out as the best performing exact solutions for the Maximum Clique problem. The main recent advances are basically refinements on the same algorithm, where heuristic coloring functions are used for bounding. We look into an attempt to get a tighter bound by applying an heuristic employed in MaxSat solvers.
Autores: Alexandre Prusch Züge, Renato Carmo

Download

O problema da partipação em cliques-dominantes

Dado um grafo G, uma partição em cliques-dominantes (PCD) é uma partição de V (G) tal que cada uma de suas partes seja um conjunto clique-dominante. O problema da partição em cliques-dominantes consiste em determinar dcl(G) = max{|Pj| : P é uma PCD de G}.
Autor:H. V. e Sousa, C. N. Campos

Download

Forbidden subgraph characterization of extended star directed path graphs that are not rooted directed path graphs

An asteroidal triple in a graph is a set of three non-adjacent vertices such that for any two of them there exists a path between them that does not intersect the neighborhood of the third. An asteroidal quadruple is a set of four non-adjacent vertices such that any three of them is an asteroidal triple.
Autor:M. Gutierrez, S. B. Tondato

Download

On the diameter of the Cayley Graph Hlp

The family Hlp has been defined in the context of edge partitions. Subsequently, it was shown to be composed of Hamiltonian Cayley graphs, and that it is possible to determine the diameter of Hlp in O(l) time. The established properties such as the low diameter suggest the Hlp graph as a good topology for the design of interconnection networks.
Autores:Diane Castonguay, André da C. Ribeiro, Luis Antonio B. Kowada, Celina M. H. de Figueiredo

Download

Complexity of Comparing the Domination Number to the Independent Domination, Connected Domination, and Paired Domination Numbers

Very little is known about the graphs that satisfy one of these inequalities with equality. I.E. Zverovich and V.E. Zverovich studied classes of graphs defined by requiring equality in one of the first two above inequalities for all induced subgraphs (without isolated vertices, if necessary). In this
article we prove hardness results which suggest that the extremal graphs for some of the above inequalities do not have a simple structure.
Autores:José D. Alvarado, Simone Dantas, Dieter Rautenbach

Download

New Results of the Geodeticity of the Contour of a Graph

Using computational tools, we show that, if there exists a positive answer for the problem (ii) of Cáceres et al. 2005, the graph must
contain at least 11 vertices.
Autores:Danilo Artigas, Simone Dantas, Alonso L. S. Oliveira, Thiago M. D. Silva

Download

Constructing pairs of Laplacian equienergetic threshold graphs

The Laplacian energy of a graph G on n vertices and m edges is defined as the sum of absolute values of the differences between
each Laplacian eigenvalue of G and the average degree 2m=n. In this work we construct pairs of threshold graphs of same order, with same Laplacian energy and different sets of Laplacian eigenvalues.
Autores:R. R. Del-Vecchio, G. B. Pereira, C. T. M. Vinagre

Download

O Número de Helly Geodético em Convexidades

Um conjunto de vértices S de um grafo G é geodesicamente convexo se os vértices de todo caminho mínimo entre vértices de S
pertencem a S. O número de Helly é o menor inteiro k para o qual toda família k-intersectante C de conjuntos convexos de G possui um vértice comum aos conjuntos de C. Determinamos o número de Helly para árvores, d-grades completas, ciclos, completos e k-partidos completos. Apresentamos também dois limitantes inferiores.
Autor:Moisés Teles Carvalho Junior, Mitre Costa Dourado, Jayme Luiz Szwarcfiter

Download

On the l-neighborhood convexity

We determine the hull number for cographs in the 3-neighborhood convexity and determine the Carathéodory number of trees for l-neighborhood convexity, where l > 2.
Autores:Carmen C. Centeno, Erika M. M. Coelho, Mitre C. Dourado, Jayme L. Szwarcfiter

Download

On the minimum neighborhood of independent sets in the n-cube

We present a lower and an upper bound for Opt(n,l). These bounds are found to have the same values for a large number of instances, encouraging us to conjecture that either bound is actually Opt(n,l).
Autores:Moysés da S. Sampaio Júnior, Fabiano de S. Oliveira, Luérbio Faria, Paulo E. D. Pinto

Download

An Experimental Analysis of Exact Algorithms for the Maximum Clique Problem

We perform an experimental analysis of 10 exact algorithms for the Maximum Clique problem. The comparative results reported imply that, when solving a particular maximum clique problem, if the focus is on minimizing the number of branching steps, the x+df algorithm is the best option. However, if running time is the main concern, then the dyn algorithm is the best choice.
Autores:Cleverson Sebastião dos Anjos, Alexandre Prusch Züge, Renato Carmo

Download

Polynomial enumeration of chordless cycles on cyclically orientable graphs

In a finite undirected simple graph, a chordless cycle is an induced subgraph which is a cycle. A graph is called cyclically orientable if
it admits an orientation in which every chordless cycle is cyclically oriented. We propose an algorithm to enumerate all chordless cycles of such a graph. Compared to other similar algorithms, the proposed algorithm has the advantage of finding each chordless cycle only once in time complexity O(n2), where n is the number of vertices.
Autores:Diane Castonguay, Elisângela Silva Dias

Download

Complexity of the oriented coloring in planar, cubic oriented graphs

In this work we prove that ocn4 remains NP-complete even when restricted to a connected, planar and cubic oriented graph G.
Autores:Hebert Coelho, Luerbio Faria, Sylvain Gravier, Sulamita Klein

Download