Strong edge-coloring of graphs with maximum degree 4 using 22 colors

In 1985, Erd?s and Ne?etril conjectured that the strong edge-coloring number of a graph is bounded above by when Δ is even and when Δ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for Δ?3. For Δ=4, the conjectured bound is 20. Previously, the best known upper bound was 23 due to Horak. In this paper we give an algorithm that uses at most 22 colors.     

Total domination and total domination subdivision number of a graph and its complement

A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγ_t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersd_γt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n?4, minimum degree δ and maximum degree Δ. We prove that if each component of G and has order at least 3 and , then and if each component of G and has order at least 2 and at least one component of G and has order at least 3, then . We also give a result on stronger than a conjecture by Harary and Haynes.     

Edge-recognizable domination numbers

For any undirected graph G, let be the collection of edge-deleted subgraphs. It is always possible to construct a graph H from so that . The general edge-reconstruction conjecture states that G and H must be isomorphic if they have at least four edges. A graphical invariant that must be identical for all graphs that can be constructed from the given collection is said to be edge-recognizable. Here we show that the domination number and many of its common variations are edge-recognizable.     

Nomadic decompositions of bidirected complete graphs

We use to denote the bidirected complete graph on n vertices. A nomadic Hamiltonian decomposition of is a Hamiltonian decomposition, with the additional property that “nomads” walk along the Hamiltonian cycles (moving one vertex per time step) without colliding. A nomadic near-Hamiltonian decomposition is defined similarly, except that the cycles in the decomposition have length n-1, rather than length n. Bondy asked whether these decompositions of exist for all n. We show that admits a nomadic near-Hamiltonian decomposition when .     

Long alternating paths in bicolored point sets

Given n red and n blue points in convex position in the plane, we show that there exists a noncrossing alternating path of length . We disprove a conjecture of Erd?s by constructing an example without any such path of length greater than .     

On NP-hardness of the clique partition—Independence number gap recognition and related problems

We show that for a graph G it is NP-hard to decide whether its independence number α(G) equals its clique partition number even when some minimum clique partition of G is given. This implies that any α(G)-upper bound provably better than is NP-hard to compute.To establish this result we use a reduction of the quasigroup completion problem (QCP, known to be NP-complete) to the maximum independent set problem. A QCP instance is satisfiable if and only if the independence number α(G) of the graph obtained within the reduction is equal to the number of holes h in the QCP instance. At the same time, the inequality always holds. Thus, QCP is satisfiable if and only if . Computing the Lovász number ?(G) we can detect QCP unsatisfiability at least when . In the other cases QCP reduces to gap recognition, with one minimum clique partition of G known.     

On the number of graphs with a given endomorphism monoid

For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .     

Hamilton decompositions of directed cubes and products

Call a directed graph symmetric if it is obtained from an undirected graph G by replacing each edge of G by two directed edges, one in each direction. We will show that if G has a Hamilton decomposition with certain additional structure, then has a directed Hamilton decomposition. In particular, it will follow that the bidirected cubes for m?2 are decomposable into 2m+1 directed Hamilton cycles and that a product of cycles is decomposable into 2m+1 directed Hamilton cycles if n_i?3 and m?2.     

On sums of binomial coefficients and their applications

In this paper we study recurrences concerning the combinatorial sum and the alternate sum , where m>0, n?0 and r are integers. For example, we show that if n?m-1 then

     

Coloring the complements of intersection graphs of geometric figures

Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rⁿ. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rⁿ.     

Distance irredundance and connected domination numbers of a graph

Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γ_k(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number ir_k(G). The authors prove that if an ir_k-set X is a k-independent set of G, then , and that for k?2, if ir_k(G)=1, if ir_k(G) is odd, and if ir_k(G) is even, which generalize some known results.     

On the asymptotic number of inequivalent binary self-dual codes

Let Ψn be the number of inequivalent self-dual codes in . We prove that , where . Let Δn be the number of inequivalent doubly even self-dual codes in . We also prove that .     

How to play the Majority game with a liar

The Majority game is played by a questioner () and an answerer (). holds n elements, each of which can be labeled as 0 or 1. is trying to identify some element holds as having the Majority label or, in the case of a tie, claim there is none. To do this asks questions comparing whether two elements have the same or different label. ’s goal is to ask as few questions as possible while ’s goal is to delay as much as possible. Let q^∗ denote the minimal number of questions needed for to identify a Majority element regardless of ’s answers.In this paper we investigate upper and lower bounds for q^∗ in a variation of the Majority game, where is allowed to lie up to t times. We consider two versions of the game, the adaptive (where questions are asked sequentially) and the oblivious (where questions are asked in one batch).     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .     

On conjugate adjacency matrices of a graph

Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A^c=[c_ij] is the conjugate adjacency matrix of the graph G if c_ij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and c_ij=0 if i=j. Let P_G(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if P_G(λ)=P_H(λ) and . Further, let P^c(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs G_i=G?i(i=1,2,…,n). If P^c(G)=P^c(H) we prove that , provided that the order of G is greater than 2.     

List-edge and list-total colorings of graphs embedded on hyperbolic surfaces

In the paper, we prove that if G is a graph embeddable on a surface of Euler characteristic ε<0 and , then and . This extends a result of Borodin, Kostochka and Woodall [O.V. Borodin, A.V. Kostochka, D.R. Woodall, List-edge and list-total colorings of multigraphs, J. Comb. Theory Series B 71 (1997) 184-204].     

On a conjecture of Erd?s, Graham and Spencer, II

It is conjectured by Erd?s, Graham and Spencer that if 1≤a₁≤a₂≤?≤a_s are integers with , then this sum can be decomposed into n parts so that all partial sums are ≤1. This is not true for as shown by a₁=?=a_n−2=1, . In 1997 Sandor proved that Erd?s-Graham-Spencer conjecture is true for . Recently, Chen proved that the conjecture is true for . In this paper, we prove that Erd?s-Graham-Spencer conjecture is true for .     

On wreathed lexicographic products of graphs

This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G.     

Graph colourings and solutions of systems of equations over finite fields

A congruence (p is a prime) is said to be strong homogeneous if it has the form

     

On a relation between certain cohomological invariants

Let G be a group, the supremum of the projective lengths of the injective ZG-modules and the supremum of the injective lengths of the projective ZG-modules. The invariants and were studied in [T.V. Gedrich, K.W. Gruenberg, Complete cohomological functors on groups, Topology Appl. 25 (1987) 203-223] in connection with the existence of complete cohomological functors. If is finite then [T.V. Gedrich, K.W. Gruenberg, Complete cohomological functors on groups, Topology Appl. 25 (1987) 203-223] and , where is the generalized cohomological dimension of G [B.M. Ikenaga, Homological dimension and Farrell cohomology, J. Algebra 87 (1984) 422-457]. Note that if G is of finite virtual cohomological dimension. It has been conjectured in [O. Talelli, On groups of type Φ, Arch. Math. 89 (1) (2007) 24-32] that if is finite then G admits a finite dimensional model for , the classifying space for proper actions.We conjecture that for any group G and we prove the conjecture for duality groups, fundamental groups of graphs of finite groups and fundamental groups of certain finite graphs of groups of type .