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
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
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.
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
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
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.
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
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.
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
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
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.
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
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
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
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
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
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
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.
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
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.
contain at least 11 vertices.
Autores:Danilo Artigas, Simone Dantas, Alonso L. S. Oliveira, Thiago M. D. Silva
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.
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
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.
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
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
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
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
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.
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
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