 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 10 no. 1
1. Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D.
Section:
Graph and Algorithms
2. Interaction properties of relational periods
We consider relational periods where the relation is a compatibility relation on words induced by a relation on letters. We introduce three types of periods, namely global, external and local relational periods, and we compare their properties by proving variants of the theorem of Fine and Wilf for these periods.
Section:
Automata, Logic and Semantics
3. On quadratic residue codes and hyperelliptic curves
For an odd prime p and each non-empty subset S ⊂ GF(p), consider the hyperelliptic curve X_S defined by y^2 = f_s(x), where f_s(x) = \P_{a2S} (x-a). Using a connection between binary quadratic residue codes and hyperelliptic curves over GF(p), this paper investigates how coding theory bounds give rise to bounds such as the following example: for all sufficiently large primes p there exists a subset S ⊂ GF(p) for which the bound |X_S(GF(p))| > 1.39p holds. We also use the quasi-quadratic residue codes defined below to construct an example of a formally self-dual optimal code whose zeta function does not satisfy the "Riemann hypothesis."
Section:
Combinatorics
4. Sufficient conditions for labelled 0-1 laws
If F(x) = e^G(x), where F(x) = \Sum f(n)x^n and G(x) = \Sum g(n)x^n, with 0 ≤ g(n) = O(n^θn/n!), θ ∈ (0,1), and gcd(n : g(n) > 0) = 1, then f(n) = o(f(n − 1)). This gives an answer to Compton's request in Question 8.3 [Compton 1987] for an "easily verifiable sufficient condition" to show that an adequate class of structures has a labelled first-order 0-1 law, namely it suffices to show that the labelled component count function is O(n^θn) for some θ ∈ (0,1). It also provides the means to recursively construct an adequate class of structures with a labelled 0-1 law but not an unlabelled 0-1 law, answering Compton's Question 8.4.
Section:
Combinatorics
5. Total domination in K₅- and K₆-covered graphs
A graph G is Kr-covered if each vertex of G is contained in a Kr-clique. Let $\gamma_t(G)$ denote the total domination number of G. It has been conjectured that every Kr-covered graph of order n with no Kr-component satisfies $\gamma_t(G) \le \frac{2n}{r+1}$. We prove that this conjecture is true for r = 5 and 6.
Section:
Graph and Algorithms
6. Bounded-degree graphs have arbitrarily large queue-number
It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all \Delta ≥ 3 and for all sufficiently large n, there is a simple \Delta-regular n-vertex graph with queue-number at least c√\Delta_n^{1/2-1/\Delta} for some absolute constant c.
Section:
Graph and Algorithms
7. The Laplacian spread of a tree
The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of the Laplacian matrix of the graph. In this paper, we show that the star is the unique tree with maximal Laplacian spread among all trees of given order, and the path is the unique one with minimal Laplacian spread among all trees of given order.
Section:
Graph and Algorithms
8. On hereditary Helly classes of graphs
In graph theory, the Helly property has been applied to families of sets, such as cliques, disks, bicliques, and neighbourhoods, leading to the classes of clique-Helly, disk-Helly, biclique-Helly, neighbourhood-Helly graphs, respectively. A natural question is to determine for which graphs the corresponding Helly property holds, for every induced subgraph. This leads to the corresponding classes of hereditary clique-Helly, hereditary disk-Helly, hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. In this paper, we describe characterizations in terms of families of forbidden subgraphs, for the classes of hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. We consider both open and closed neighbourhoods. The forbidden subgraphs are all of fixed size, implying polynomial time recognition for these classes.
Section:
Graph and Algorithms
9. Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D.
Section:
Graph and Algorithms
10. Recurrence among trees with most numerous efficient dominating sets
A dominating set D of vertices in a graph G is called an efficient dominating set if the distance between any two vertices in D is at least three. A tree T of order n is called maximum if T has the largest number of efficient dominating sets among all n-vertex trees. A constructive characterization of all maximum trees is given. Their structure has recurring aspects with period 7. Moreover, the number of efficient dominating sets in maximum n-vertex trees is determined and is exponential. Also the number of maximum n-vertex trees is shown to be bounded below by an increasing exponential function in n.
Section:
Graph and Algorithms
11. VC-dimensions of random function classes
For any class of binary functions on [n]={1, ..., n} a classical result by Sauer states a sufficient condition for its VC-dimension to be at least d: its cardinality should be at least O(nd-1). A necessary condition is that its cardinality be at least 2d (which is O(1) with respect to n). How does the size of a 'typical' class of VC-dimension d compare to these two extreme thresholds ? To answer this, we consider classes generated randomly by two methods, repeated biased coin flips on the n-dimensional hypercube or uniform sampling over the space of all possible classes of cardinality k on [n]. As it turns out, the typical behavior of such classes is much more similar to the necessary condition; the cardinality k need only be larger than a threshold of 2d for its VC-dimension to be at least d with high probability. If its expected size is greater than a threshold of O(&log;n) (which is still significantly smaller than the sufficient size of O(nd-1)) then it shatters every set of size d with high probability. The behavior in the neighborhood of these thresholds is described by the asymptotic probability distribution of the VC-dimension and of the largest d such that all sets of size d are shattered.
Section:
Combinatorics
12. Strong Oriented Chromatic Number of Planar Graphs without Short Cycles
Let M be an additive abelian group. An M-strong-oriented coloring of an oriented graph G is a mapping f from V(G) to M such that f(u) <> j(v) whenever uv is an arc in G and f(v)−f(u) <> −(f(t)−f(z)) whenever uv and zt are two arcs in G. The strong oriented chromatic number of an oriented graph is the minimal order of a group M such that G has an M-strong-oriented coloring. This notion was introduced by Nesetril and Raspaud [Ann. Inst. Fourier, 49(3):1037-1056, 1999]. We prove that the strong oriented chromatic number of oriented planar graphs without cycles of lengths 4 to 12 (resp. 4 or 6) is at most 7 (resp. 19). Moreover, for all i ≥ 4, we construct outerplanar graphs without cycles of lengths 4 to i whose oriented chromatic number is 7.