Netlike partial cubes III. The median cycle property

A graph G has the Median Cycle Property (MCP) if every triple (u₀,u₁,u₂) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if x_i is the gate of u_i in C, then: {x_i,x_j}⊆I_G(u_i,u_j) if i≠j, and d_G(x_i,x_j)<d_G(x_i,x_k)+d_G(x_k,x_j). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K₁ by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).     

Walking in circles

Consider the unit circle S¹ with distance function d measured along the circle. We show that for every selection of 2n points x₁,…,x_n,y₁,…,y_n∈S¹ there exists i∈{1,…,n} such that . We also discuss a game theoretic interpretation of this result.     

Kernels in quasi-transitive digraphs

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.A kernel N of D is an independent set of vertices such that for every w∈V(D)-N there exists an arc from w to N. A digraph is called quasi-transitive when (u,v)∈A(D) and (v,w)∈A(D) implies (u,w)∈A(D) or (w,u)∈A(D). This concept was introduced by Ghouilá-Houri [Caractérisation des graphes non orientés dont on peut orienter les arrêtes de maniere à obtenir le graphe d’ un relation d’ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371] and has been studied by several authors. In this paper the following result is proved: Let D be a digraph. Suppose D=D₁∪D₂ where D_i is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in D_i) for i∈{1,2}; and that every directed cycle of length 3 contained in D has at least two symmetrical arcs, then D has a kernel. All the conditions for the theorem are tight.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Nonsingularity of least common multiple matrices on gcd-closed sets

Let n be a positive integer. Let S={x₁,…,x_n} be a set of n distinct positive integers. The least common multiple (LCM) matrix on S, denoted by [S], is defined to be the n×n matrix whose (i,j)-entry is the least common multiple [x_i,x_j] of x_i and x_j. The set S is said to be gcd-closed if for any x_i,x_j∈S,(x_i,x_j)∈S. For an integer m>1, let ω(m) denote the number of distinct prime factors of m. Define ω(1)=0. In 1997, Qi Sun conjectured that if S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. In this paper, we settle completely Sun's conjecture. We show the following result: (i). If S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. Namely, Sun's conjecture is true; (ii). For each integer r?3, there exists a gcd-closed set S satisfying max_x∈S{ω(x)}=r, such that the LCM matrix [S] is singular.     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOM(H).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D) is associated with costs c_i(u),i∈V(H), then the cost of the homomorphism f is ∑_u∈V(D)c_f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem forH and denote it as MinHOM(H). The problem is to decide, for an input graph D with costs c_i(u),u∈V(D),i∈V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].     

Minimum cost and list homomorphisms to semicomplete digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). Let H be a fixed directed or undirected graph. The homomorphism problem for H asks whether a directed or undirected input graph D admits a homomorphism to H. The list homomorphism problem for H is a generalization of the homomorphism problem for H, where every vertex x∈V(D) is assigned a set L_x of possible colors (vertices of H).The following optimization version of these decision problems generalizes the list homomorphism problem and was introduced in Gutin et al. [Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., to appear], where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs D,H and a positive integral cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is . For a fixed digraph H, the minimum cost homomorphism problem for H is stated as follows: for an input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if one exists, find such a homomorphism of minimum cost.We obtain dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when H is a semicomplete digraph (digraph in which there is at least one arc between any two vertices). Our dichotomy for the list homomorphism problem coincides with the one obtained by Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when H is a semicomplete digraph: both problems are polynomial solvable if H has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for the minimum cost homomorphism problem is different: the problem is polynomial time solvable if H is acyclic or H is a cycle of length 2 or 3; otherwise, the problem is NP-hard.     

Solution of a system of functional-differential equations arising from an optimization problem

In connection with an optimization problem, all functions ?: Iⁿ → $\text{R}$ with continuous nonzero partial derivatives and satisfying

$\text{??}\text{?x,}{}_{\mathrm{i}}\text{??}\text{?x}{}_{\mathrm{j}}$

for all x_i, x_j ≠ I, i, j = 1,2,…, n (n > 2) are determined (I is an interval of positive real numbers).     

Minimum cost homomorphisms to semicomplete multipartite digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism ofDtoH if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed directed or undirected graph H and an input graph D, the problem of verifying whether there exists a homomorphism of D to H has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced recently by the authors and M. Tso.Suppose we are given a pair of digraphs D,H and a cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is ∑_u∈V(D)c_f(u)(u). Let H be a fixed digraph. The minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of when H is a semicomplete digraph. In this paper we extend the classification to semicomplete k-partite digraphs, k≥3, and obtain such a classification for bipartite tournaments.     

An extension of Birkhoff’s theorem with an application to determinants

Let M_n(F) denote the algebra of n×n matrices over the field F of complex, or real, numbers. Given a self-adjoint involution J∈M_n(C), that is, J=J^*,J²=I, let us consider Cⁿ endowed with the indefinite inner product [,] induced by J and defined by [x,y]?〈Jx,y〉,x,y∈Cⁿ. Assuming that (r,n-r), 0?r?n, is the inertia of J, without loss of generality we may assume J=diag(j₁,?,j_n)=I_r⊕-I_n-r. For T=(|t_ik|²)∈M_n(R), the matrices of the form T=(|t_ik|²j_ij_k), with all line sums equal to 1, are called J-doubly stochastic matrices. In the particular case r∈{0,n}, these matrices reduce to doubly stochastic matrices, that is, non-negative real matrices with all line sums equal to 1. A generalization of Birkhoff’s theorem on doubly stochastic matrices is obtained for J-doubly stochastic matrices and an application to determinants is presented.     

Existence of solutions for degenerate quasilinear elliptic equations

This paper deals with a class of degenerate quasilinear elliptic equations of the form −div(a(x,u,∇u)=g−div(f), where a(x,u,∇u) is allowed to be degenerate with the unknown u. We prove existence of bounded solutions under some hypothesis on f and g. Moreover we prove that there exists a renormalized solution in the case where g∈L¹(Ω) and f∈(L^p′(Ω))^N.     

Characterization of the absence of a spectral gapfor a class of periodic Jacobi operators

Let q ∈ {2, 3} and let 0 = s₀ < s₁ < … < s_q = T be integers. For m, n ∈ Z, we put ¯m,n = {j ∈ Z| m? j ? n}. We set l_j = s_j − s_j−1 for j ∈ 1, q. Given (p₁,, p_q) ∈ R^q, let b: Z → R be a periodic function of period T such that b(·) = p_j on s_j−1 + 1, s_j for each j ∈ 1, q. We study the spectral gaps of the Jacobi operator (Ju)(n) = u(n + 1) + u(n − 1) + b(n)u(n) acting on l²(Z). By [λ_2j , λ_2j−1] we denote the jth band of the spectrum of J counted from above for j ∈ 1, T. Suppose that p_m ≠ p_n for m ≠ n. We prove that the statements (i) and (ii) below are equivalent for λ ∈ R and i ∈ 1, T − 1.     

Nonsingularity of matrices associated with classes of arithmetical functions on lcm-closed sets

Let S = {x₁, … , x_n} be a set of n distinct positive integers and f be an arithmetical function. Let [f(x_i, x_j)] denote the n × n matrix having f evaluated at the greatest common divisor (x_i, x_j) of x_i and x_j as its i, j-entry and (f[x_i, x_j]) denote the n × n matrix having f evaluated at the least common multiple [x_i, x_j] of x_i and x_j as its i, j-entry. The set S is said to be lcm-closed if [x_i, x_j] ∈ S for all 1 ? i, j ? n. For an integer x > 1, let ω(x) denote the number of distinct prime factors of x. Define ω(1) = 0. In this paper, we show that if S = {x₁, … , x_n} is an lcm-closed set satisfying , and if f is a strictly increasing (resp. decreasing) completely multiplicative function, or if f is a strictly decreasing (resp. increasing) completely multiplicative function satisfying (resp. f(p) ? p) for any prime p, then the matrix [f(x_i, x_j)] (resp. (f[x_i, x_j])) defined on S is nonsingular. By using the concept of least-type multiple introduced in [S. Hong, J. Algebra 281 (2004) 1-14], we also obtain reduced formulas for det(f(x_i, x_j)) and det(f[x_i, x_j]) when f is completely multiplicative and S is lcm-closed. We also establish several results about the nonsingularity of LCM matrices and reciprocal GCD matrices.     

Estimates for Emden-Fowler type inequalities with absorption term

We obtain improved estimates of the Keller-Osserman type for second-order elliptic semilinear inequalities in the non-divergent form sign(u)(aij(x)uxixj+bi(x)uxi)?c(x)⁻²|x|σ|u|. Special cases of rapidly growing or decaying weights c(x) and planar domains are also treated.     

Tournament immersion and cutwidth

A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered {v₁,…,vn} in such a way that for each j, there are at most k edges uv such that u∈{v₁,…,vj−1} and v∈{vj,…,vn}.We prove that for every set S of tournaments, the following are equivalent:

•

there is a digraph H such that H cannot be strongly immersed in any member of S,

•

there exists k such that every member of S has cutwidth at most k,

•

there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles.

This is a key lemma towards two results that will be presented in later papers: first, that strong immersion is a well-quasi-order for tournaments, and second, that there is a polynomial time algorithm for the k edge-disjoint directed paths problem (for fixed k) in a tournament.     

Steiner intervals, geodesic intervals, and betweenness

The concept of the k-Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping S:V×?×V?2^V such that S(u₁,…,u_k) consists of all vertices in G that lie on some Steiner tree with respect to a multiset W={u₁,…,u_k} of vertices from G. In this paper we obtain, for each k, a characterization of the class of graphs in which every k-Steiner interval S has the so-called union property, which says that S(u₁,…,u_k) coincides with the union of geodesic intervals I(u_i,u_j) between all pairs from W. It turns out that, as soon as k>3, this class coincides with the class of graphs in which the k-Steiner interval enjoys the monotone axiom (m), respectively (b2) axiom, the conditions from betweenness theory. Notably, S satisfies (m), if x₁,…,x_k∈S(u₁,…,u_k) implies S(x₁,…,x_k)⊆S(u₁,…,u_k), and S satisfies (b2) if x∈S(u₁,u₂,…,u_k) implies S(x,u₂,…,u_k)⊆S(u₁,…,u_k). In the case k=3, these three classes are different, and we give structural characterizations of graphs for which their Steiner interval S satisfies the union property as well as the monotone axiom (m). We also prove several partial observations on the class of graphs in which the 3-Steiner interval satisfies (b2), which lead to the conjecture that these are precisely the graphs in which every block is a geodetic graph with diameter at most two.     

Divisibility properties of power LCM matrices by power GCD matrices on gcd-closed sets

Let e and n be positive integers and S={x₁,…,x_n} a set of n distinct positive integers. For x∈S, define . The n×n matrix whose (i,j)-entry is the eth power (x_i,x_j)^e of the greatest common divisor of x_i and x_j is called the eth power GCD matrix on S, denoted by (S^e). Similarly we can define the eth power LCM matrix [S^e]. Bourque and Ligh showed that (S)∣[S] holds in the ring of n×n matrices over the integers if S is factor closed. Hong showed that for any gcd-closed set S with |S|≤3, (S)∣[S]. Meanwhile Hong proved that there is a gcd-closed set S with max_x∈S{|G_S(x)|}=2 such that (S)?[S]. In this paper, we introduce a new method to study systematically the divisibility for the case max_x∈S{|G_S(x)|}≤2. We give a new proof of Hong’s conjecture and obtain necessary and sufficient conditions on the gcd-closed set S with max_x∈S{|G_S(x)|}=2 such that (S^e)|[S^e]. This partially solves an open question raised by Hong. Furthermore, we show that such factorization holds if S is a gcd-closed set such that each element is a prime power or the product of two distinct primes, and in particular if S is a gcd-closed set with every element less than 12.     

Directed defective asymmetric graph coloring games

We consider the following 2-person game which is played with an (initially uncolored) digraph D, a finite color set C, and nonnegative integers a, b, and d. Alternately, player I colors a vertices and player II colors b vertices with colors from C. Whenever a player colors a vertex v, all in-arcs (w,v) that do not come from a vertex w previously colored with the same color as v are deleted. For each color i the defect digraphD_i is the digraph induced by the vertices of color i at a certain state of the game. The main rule the players have to respect is that at every time for any color i the digraph D_i has maximum total degree of at most d. The game ends if no vertex can be colored any more according to this rule. Player I wins if D is completely colored at the end of the game, otherwise player II wins. The smallest cardinality of a color set C with which player I has a winning strategy for the game is called . This parameter generalizes several variants of Bodlaender’s game chromatic number. We determine the tight (resp., nearly tight) upper bound (resp., ) for the d-relaxed (a,b)-game chromatic number of orientations of forests (resp., undirected forests) for any d and a≥b≥1. Furthermore we prove that these numbers cannot be bounded in case a<b.