Volume 42 – 2012 – 5th Latin-American Workshop on Cliques in Graphs

Articles

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

Autores:Celina M. H. de Figueiredo, Marina Groshaus, Fábio Protti, Francisco Soulignac

Download

Interval Count of Generalizations of Threshold Graphs

The interval count is the smallest number of distint interval lengths over all models of a particular interval graph. Although the graphs having interval count one are well-known since the sixties, very few is known aboutthe graphs having interval count k ≥ 2, even for fixed k. Recently, a polynomial-time algorithm has been presented to compute the interval count of extended-bull-free graphs, letting open the efficient computation of interval count of graphs in which extended-bulls may exist.
Autores:M. R. Cerioli, F. de S. Oliveira, J. L. Szwarcfiter

Download

Strong reducibility of Solitaire Clobber played on Cartesian product of graphs

Solitaire Clobber is a game played on a graph G by placing a stone, black or white, on each vertex of the graph. We pick up a stone and clobber another one of opposite color located on an adjacent vertex; the clobbered stone is removed from the graph and it is replaced by the picked one.
Autores:Simone Dantas, Sylvain Gravier, Telma Pará

Download

DV-model that can be rooted

A graph G is a directed (respectively rooted directed) path graph or a DV (RDV) graph if it admits a DV-model (RDV-model), i.e a clique tree T whose edges can be directed (directed from a root towards the leaves)such thatfor every vertex of G the subtree induced by the cliquesthat contain it is a directed subpath of T. An interval graph is the intersection graph of a family of subpaths of a path.
Autores:Marisa Gutierrez, Silvia B Tondato

Download

AVD-total-colouring of complete equipartite graphs

An AVD-total-colouring of a simple graph G is a mapping φ : V (G) ∪ E(G) → C, with C a set of colours, such that: (i) for each adjacent or incident elements x,y ∈ V (G) ∪ E(G), φ(x) ?= φ(y); (ii) and for each pair of adjacent vertices x,y ∈ V (G), sets {φ(x)}∪ {φ(xv): xv ∈ E(G)} and {φ(y)}∪{φ(yv): yv ∈ E(G)} are distincts. The AVD-total-chromatic number, χ”a(G), is the smallest number of colours for which G admits an AVD-total-colouring.
Autores:A. G. Luiz, C. N. Campos, C. P. de Mello

Download

Independence in Graphs A Medley of Popular Tunes

We survey some recent developments related to three classical lower bounds on the independence number of graphs; Caro’s and Wei’s bound for general graphs, Shearer’s bound for triangle-free graphs, and Staton’s bound for triangle-free graphs of maximum degree at most three. We discuss these bounds, their proofs, and some of our own research that evolved around them.
Autores:Dieter Rautenbach

Download

Multicolored Ramsey Numbers in Multipartite Graphs

Let Kr denote the complete graph on r vertices. Given positive integers n1 ≥ 2 and n2 ≥ 2, recall that the celebrated Ramsey number r(n1,n2) denotesthe smallest natural number r such that every red-blue coloring of the edges of Kr yields a red copy of Kn1 or a blue copy of Kn2. Determining Ramsey numbers has been a great challenge in graph theory
Autores:Juliana Sanches, E.L. Monte Carmelo

Download

Searching for a NP-Complete Probe Graph Problem

A probe graph for a graph class C is a graph G = (V,E),such that it is possible to add some edges between vertices of an independent set N in order to obtain a graph G? belonging to C [7]. If the independent set N c V is given asinput, we have a special case of graph sandwich problem [6], called partitioned probe problem. A graph partition of a graph G = (V,E) is a partition of V into a number of parts
Autores:R. B. Teixeira, C. M. H. de Figueiredo, S. Dantas

Download

EPT graphs 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. In this paper, we answer negatively the question posed by Golumbic et al. [4]: Can any EPT graph without induced cycles of size greater than h be represented in a host tree with maximum degree h?
Autores:Liliana Alcón, Marisa Gutierrez, María Pía Mazzoleni

Download

Sandwich Problems: why not ask for special kinds of bread?

In this work, we consider the Golumbic, Kaplan, and Shamir decision sandwich problem for a property II:given two graphs G1 = (V,E1) and G2 = (V,E2), the question is: Is there a graph G = (V,E) such that E1 c E c E2 and G satisfies II? The graph G is called sandwich graph. Note that what matters here is just the “filling” of the sandwich.
Autores:F. Couto, L. Faria, S. Klein, F. Protti, L. T. Nogueira

Download

Design of connection networks with bounded number of non-terminal vertices

The spanning tree problem and the steiner tree problem aim at obtaining an acyclic subgraph connecting a set of terminal points and satisfying some properties. Both problems have several important network applications.
Autores:Mitre C. Dourado, Rodolfo A. Oliveira, Fábio Protti, Uéverton S. Souza

Download

Characterizing Clique Graphs of Chordal Comparability Graphs

The clique graph K(G) of a graph G is the intersection graph of the maximal cliques of G. A well-known characterization of clique graphs is that by Roberts and Spencer (1971). In addition there are characterizations for clique graphs of several graph classes.
Autores:Michel Habib, Denis Julien, Ross M. McConnell, Vin´ıcius F. dos Santos

Download

Integer index of p-broom-like graphs

A p-broom-like graph is obtained by identifying each vertex of a p-clique with the root of a copy of a rooted broom. We prove that the class of p-broom-like graphs with n vertices is total and strictly ordered by the index (the largest eigenvalue ofthe adjacency matrix). Moreover, for p-broom-like maximal graphs (higher index) we obtain integrality conditions, both for the index as for the graph itself, proving the existence of an integral p-broom-like graph for each p-clique with p ≥ 5.
Autores:Laura Patuzzi, Maria Aguieiras A. de Freitas, Renata R. Del-Vecchio

Download

Two Families of Cayley Graph Interconnection Networks

The family Hl,p has been defined in the context of edge partitions, and subsequently shown to be composed by Hamiltonian Cayley graphs. The pl−1 vertices of the graph Hl,p are the l-tuples with values between 0 and p − 1, such that the sum of the l values is congruent to 0 mod p, and there is an edge between two vertices having two corresponding pairs of entries whose values differ by one unit.
Autores:André da C. Ribeiro, Luis Antonio B. Kowada, Celina M. H. de Figueiredo

Download

Total chromatic number of some families of graphs with maximum degree 3

The focus of this work is the total coloring of graphs with maximum degree 3. We 4-total-color five infinite families with maximum degree 3: a new infinite family of snarks constructed from Blanusa snarks; two new infinite families of cubic graphs constructed from 4-Möbius-ladder and 5-ladder, respectively; and two grid families,Hexagonal-grid and Pentagonal-grid.
Autores:D. Sasaki, S. Dantas, C. M. H. de Figueiredo, M. Preissmann

Download