Vol. 15 no. 1


1. A bound on the number of perfect matchings in Klee-graphs

Cygan, Marek ; Pilipczuk, Marcin ; Škrekovski, Riste.
The famous conjecture of Lovász and Plummer, very recently proven by Esperet et al. (2011), asserts that every cubic bridgeless graph has exponentially many perfect matchings. In this paper we improve the bound of Esperet et al. for a specific subclass of cubic bridgeless graphs called the […]
Section: Combinatorics

2. Automaticity of primitive words and irreducible polynomials

Lacroix, Anne ; Rampersad, Narad.
If L is a language, the automaticity function A_L(n) (resp. N_L(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all inputs of length at most n. We provide bounds for the automaticity of the […]
Section: Automata, Logic and Semantics

3. Sequence variations of the 1-2-3 conjecture and irregularity strength

Seamone, Ben ; Stevens, Brett.
Karonski, Luczak, and Thomason (2004) conjecture that, for any connected graph G on at least three vertices, there exists an edge weighting from 1, 2, 3 such that adjacent vertices receive different sums of incident edge weights. Bartnicki, Grytczuk, and Niwcyk (2009) make a stronger conjecture, […]
Section: Graph Theory

4. The determining number of Kneser graphs

Cáceres, José ; Garijo, Delia ; González, Antonio ; Márquez, Alberto ; Puertas, Marıa Luz.
A set of vertices S is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G is the minimum cardinality of a determining set of G. This paper studies the determining number of Kneser graphs. First, we compute the determining […]
Section: Graph Theory

5. Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration

Eguia, Martiniano ; Soulignac, Francisco Juan.
A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every cycle […]
Section: Graph and Algorithms

6. The Erdős-Sós conjecture for geometric graphs

Barba, Luis ; Fabila-Monroy, Ruy ; Lara, Dolores ; Leaños, Jesús ; Rodrıguez, Cynthia ; Salazar, Gelasio ; Zaragoza, Francisco.
Let f(n,k) be the minimum number of edges that must be removed from some complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that ( 1 / 2 )n2 / k-1-n / 2≤f(n,k) ≤2 n(n-2) / k-2. For the case when k=n, we […]
Section: Combinatorics

7. Further results on maximal nontraceable graphs of smallest size

Burger, Alewyn Petrus ; Singleton, Joy Elizabeth.
Let g(n) denote the minimum number of edges of a maximal nontraceable (MNT) graph of order n. In 2005 Frick and Singleton (Lower bound for the size of maximal nontraceable graphs, Electronic Journal of Combinatorics, 12(1) R32, 2005) proved that g(n) = ⌈3n-22 ⌉ for n ≥54 as well as for n ∈I, where […]
Section: Graph Theory

8. List edge and list total colorings of planar graphs without non-induced 7-cycles

Dong, Aijun ; Liu, Guizhen ; Li, Guojun.
Giving a planar graph G, let χ'l(G) and χ''l(G) denote the list edge chromatic number and list total chromatic number of G respectively. It is proved that if G is a planar graph without non-induced 7-cycles, then χ'l(G)≤Δ(G)+1 and χ''l(G)≤Δ(G)+2 where Δ(G)≥7.
Section: Graph and Algorithms

9. Krausz dimension and its generalizations in special graph classes

Glebova, Olga ; Metelsky, Yury ; Skums, Pavel.
A Krausz (k,m)-partition of a graph G is a decomposition of G into cliques, such that any vertex belongs to at most k cliques and any two cliques have at most m vertices in common. The m-Krausz dimension kdimm(G) of the graph G is the minimum number k such that G has a Krausz (k,m)-partition. In […]
Section: Graph Theory

10. A chip-firing variation and a new proof of Cayley's formula

Kayll, Peter Mark ; Perkins, Dave.
We introduce a variation of chip-firing games on connected graphs. These 'burn-off' games incorporate the loss of energy that may occur in the physical processes that classical chip-firing games have been used to model. For a graph G=(V,E), a configuration of 'chips' on its nodes is a mapping C:V→ℕ. […]
Section: Graph Theory

11. All totally symmetric colored graphs

Grech, Mariusz ; Kisielewicz, Andrzej.
In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous paper, […]
Section: Graph Theory

12. Isomorphism of graph classes related to the circular-ones property

Curtis, Andrew R. ; Lin, Min Chih ; Mcconnell, Ross M. ; Nussbaum, Yahav ; Soulignac, Francisco Juan ; Spinrad, Jeremy P. ; Szwarcfiter, Jayme Luiz.
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. Our algorithm is similar to the isomorphism algorithm for interval graphs of Lueker and Booth, but works on PC trees, which are unrooted and have a cyclic nature, rather than […]
Section: Discrete Algorithms

13. The b-chromatic number of powers of cycles

Kohl, Anja.
A b-coloring of a graph G by k colors is a proper vertex coloring such that each color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number χb(G) is the maximum integer k for which G has a b-coloring by k colors. Let Cnr […]
Section: Graph Theory

14. A generic method for the enumeration of various classes of directed polycubes

Champarnaud, Jean-Marc ; Dubernard, Jean-Philippe ; Jeanne, Hadrien.
Following the track of polyominoes, in particular the column-by-column construction of Temperley and its interpretation in terms of functional equations due to Bousquet-Mélou, we introduce a generic method for the enumeration of classes of directed polycubes the strata of which satisfy some property […]
Section: Combinatorics