Strong edge colorings of uniform graphs

For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χ_s(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χ_s(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n₀(d,ε) satisfy χ_s(G)?ζ(ε)Δ(G)², where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24).     

On the domination number of the cartesian product of the cycle of length n and any graph

Let γ(G) denote the domination number of a graph G and let C_n□G denote the cartesian product of C_n, the cycle of length n?3, and G. In this paper, we are mainly concerned with the question: which connected nontrivial graphs satisfy γ(C_n□G)=γ(C_n)γ(G)? We prove that this equality can only hold if n≡1 (mod 3). In addition, we characterize graphs which satisfy this equality when n=4 and provide infinite classes of graphs for general n≡1 (mod 3).     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.     

Integers with dense divisors 2

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are t-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?t. Let D(x,t) be the number of positive integers not exceeding x whose divisors are t-dense. We show that for x?3, and , we have , where , and d(w) is a continuous function which satisfies d(w)?1/w for w?1. We also consider other counting functions closely related to D(x,t).     

Complete Multipartite Graphs and the Relaxed Coloring Game

Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted ?? _g ^d (G). It is known that there exist graphs such that ?? _g ⁰(G)?=?3, but ?? _g ¹(G)?>?3. We will show that for all positive integers m, there exists a complete multipartite graph G such that m?????? _g ⁰(G)?<??? _g ¹(G).     

The disconnection number of a graph

The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D₉, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10).     

Labeling graphs with two distance constraints

Given a graph G and integers p,q,d₁ and d₂, with p>q, d₂>d₁?1, an L(d₁,d₂;p,q)-labeling of G is a function f:V(G)→{0,1,2,…,n} such that |f(u)−f(v)|?p if d_G(u,v)?d₁ and |f(u)−f(v)|?q if d_G(u,v)?d₂. A k-L(d₁,d₂;p,q)-labeling is an L(d₁,d₂;p,q)-labeling f such that max_v∈V(G)f(v)?k. The L(d₁,d₂;p,q)-labeling number ofG, denoted by , is the smallest number k such that G has a k-L(d₁,d₂;p,q)-labeling. In this paper, we give upper bounds and lower bounds of the L(d₁,d₂;p,q)-labeling number for general graphs and some special graphs. We also discuss the L(d₁,d₂;p,q)-labeling number of G, when G is a path, a power of a path, or Cartesian product of two paths.     

All 0–1 polytopes are traveling salesman polytopes

We study the facial structure of two important permutation polytopes in , theBirkhoff orassignment polytopeB _n , defined as the convex hull of alln×n permutation matrices, and theasymmetric traveling salesman polytopeT _n , defined as the convex hull of thosen×n permutation matrices corresponding ton-cycles. Using an isomorphism between the face lattice ofB _n and the lattice of elementary bipartite graphs, we show, for example, that every pair of vertices ofB _n is contained in a cubical face, showing faces ofB _n to be fairly special 0–1 polytopes. On the other hand, we show thatevery 0–1d-polytope is affinely equivalent to a face ofT _n , fordlogn, by showing that every 0–1d-polytope is affinely equivalent to the asymmetric traveling salesman polytope of some directed graph withn nodes. The latter class of polytopes is shown to have maximum diameter [n/3].Partially supported by NSF grant DMS-9207700.     

Efficient algorithms for decomposing graphs under degree constraints

Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321-324] proved that if every vertex v in a graph G has degree d(v)?a(v)+b(v)+1 (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A,B) such that d_A(v)?a(v) for every v∈A and d_B(v)?b(v) for every v∈B. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7-9] and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237-239] strengthened this result, proving that it suffices to assume d(v)?a+b (a,b?1) or just d(v)?a+b-1 (a,b?2) if G contains no cycles shorter than 4 or 5, respectively.The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive generalizations for k-partitions are also presented.     

On the log-concavity of Hilbert series of Veronese subrings and Ehrhart series

For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write ${\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}}For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write \frach(t)(1 - t)^{d + 1}=?_{m 3 0} g(m)  t^m{\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}} , for some polynomial g(m) with rational coefficients, then \fracU_nh(t)(1- t)^d+1 = ?_{m 3 0}g(nm)  t^m{\frac{{\rm{U}}_{n}h(t)}{(1- t)^{d+1}} = \sum_{m \geq 0}g(nm) \, t^{m}} . We show that there exists a positive integer n _d , depending only on d, such that if h(t) is a polynomial of degree at most d with nonnegative integer coefficients and h(0) = 1, then for n ≥ n _d , U _n h(t) has simple, real, negative roots and positive, strictly log concave and strictly unimodal coefficients. Applications are given to Ehrhart δ-polynomials and unimodular triangulations of dilations of lattice polytopes, as well as Hilbert series of Veronese subrings of Cohen–Macauley graded rings.     

Representing simple d-dimensional polytopes by d polynomials

A polynomial representation of a convex d-polytope P is a finite set {p ₁(x), . . . , p _n (x)} of polynomials over ${\mathbb {R}^d}$ such that ${P=\{x \in \mathbb {R}^d : p_i(x) \ge 0 \mbox{ for every }1 \le i \le n\}}$ . Let s(d, P) be the least possible n as above. It is conjectured that s(d, P)?=?d for all convex d-polytopes P. We confirm this conjecture for simple d-polytopes by providing an explicit construction of d polynomials that represent a given simple d-polytope P.     

Hamiltonian path saturated graphs with small size

A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is K_n-1∪K₁. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph G_n of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and P_m-saturated graphs with small size.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

On the minimum length of ternary linear codes

From the geometrical point of view, we prove that [g ₃(6, d) + 1, 6, d]₃ codes exist for d = 118–123, 283–297 and that [g ₃(6, d), 6, d]₃ codes for d = 100, 341, 342 and [g ₃(6, d) + 1, 6, d]₃ codes for d = 130, 131, 132 do not exist, where ${g_3(k,\,d)=\sum_{i=0}^{k-1}\left\lceil d/3^i \right\rceil}$ . These determine the exact value of n ₃(6, d) for d = 100, 118–123, 130, 131, 132, 283–297, 341, 342, where n _q (k, d) is the minimum length n for which an [n, k, d] _q code exists.     

Lower bounds for the game colouring number of partial k-trees and planar graphs

This paper discusses the game colouring number of partial k-trees and planar graphs. Let col_g(PT_k) and col_g(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this paper, we prove that col_g(PT_k)=3k+2 and col_g(P)?11. We also prove that the game colouring number col_g(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then col_g(H)?col_g(G).     

Integers with dense divisors

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are y-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?y. Let D(x,y,z) be the number of positive integers not exceeding x whose divisors are y-dense and whose prime divisors are bigger than z, and let , and . We show that is equivalent, in a large region, to a function d(u,v) which satisfies a difference-differential equation. Using that equation we find that d(u,v)?(1−u/v)/(u+1) for v?3+ε. Finally, we show that d(u,v)=e^−γd(u)+O(1/v), where γ is Euler's constant and d(u)∼x⁻¹D(x,y,1), for fixed u. This leads to a new estimate for d(u).     

On a generalization of Minkowski's convex body theorem

Given a lattice $\text{Λ ? R}{}^{\mathrm{n}}$ and a bounded function g(x), x ∈ Rⁿ, vanishing outside of a bounded set, the functions ?(x)$\text{g}\text{?}\text{(x)?}$max_u∈Λg(u +x), ?(x)?Σ_{u∈Λ g(u +x)}, and ?₊(x)?Σ_u∈Λ max_{v∈Λ min {g(v + x); g(u + v + x)}} are defined and periodic mod Λ on Rⁿ. In the paper we prove that ?(x) + ?₊(x) ? 2?(x) ≥ ?(x) + h?₊(x) ? 2?(x) holds for all x ∈ Rⁿ, where h(x) is any “truncation” of g by a constant c ≥ 0, i.e., any function of the form h(x)?g(x) if g(x) ≤ c and h(x)?c if g(x) > c. This inequality easily implies some known estimations in the geometry of numbers due to Rado [1] and Cassels [2]. Moreover, some sharper and more general results are also derived from it. In the paper another inequality of a similar type is also proved.     

On embedding well-separable graphs

Call a simple graph H of order nwell-separable, if by deleting a separator set of size o(n) the leftover will have components of size at most o(n). We prove, that bounded degree well-separable spanning subgraphs are easy to embed: for every γ>0 and positive integer Δ there exists an n₀ such that if n>n₀, Δ(H)?Δ for a well-separable graph H of order n and δ(G)?(1-1/2(χ(H)-1)+γ)n for a simple graph G of order n, then H⊂G. We extend our result to graphs with small band-width, too.     

Graphs with maximum size and lower bounded girth

For integers n≥4 and ν≥n+1, let ex(ν;{C₃,…,C_n}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C₃,…,C_n}-free graphs with order ν and size ex(ν;{C₃,…,C_n}) are called extremal graphs and denoted by EX(ν;{C₃,…,C_n}). We prove that given an integer k≥0, for each n≥2log₂(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν₀(r,g);{C₃,…,C_g−1}).     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.