Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

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).     

Recognition of some symmetric groups by the set of the order of their elements

For a finite group G, let π_e(G) be the set of order of elements in G and denote S _n the symmetric group on n letters. We will show that if π_e(G ) = π_e(H), where H is S _p or S _p+1 and p is a prime with 50 < p < 100, then G ≅ H. This revised version was published online in August 2006 with corrections to the Cover Date.     

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.     

Note on robust critical graphs with large odd girth

A graph G is (k+1)-critical if it is not k-colourable but G−e is k-colourable for any edge e∈E(G). In this paper we show that for any integers k≥3 and l≥5 there exists a constant c=c(k,l)>0, such that for all , there exists a (k+1)-critical graph G on n vertices with and odd girth at least ?, which can be made (k−1)-colourable only by the omission of at least cn² edges.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

On the extension of vertex maps to graph homomorphisms

A reflexive graph is a simple undirected graph where a loop has been added at each vertex. If G and H are reflexive graphs and U⊆V(H), then a vertex map f:U→V(G) is called nonexpansive if for every two vertices x,y∈U, the distance between f(x) and f(y) in G is at most that between x and y in H. A reflexive graph G is said to have the extension property (EP) if for every reflexive graph H, every U⊆V(H) and every nonexpansive vertex map f:U→V(G), there is a graph homomorphism φ_f:H→G that agrees with f on U. Characterizations of EP-graphs are well known in the mathematics and computer science literature. In this article we determine when exactly, for a given “sink”-vertex s∈V(G), we can obtain such an extension φ_f;s that maps each vertex of H closest to the vertex s among all such existing homomorphisms φ_f. A reflexive graph G satisfying this is then said to have the sink extension property (SEP). We then characterize the reflexive graphs with the unique sink extension property (USEP), where each such sink extensions φ_f;s is unique.     

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.     

On subword decomposition and balanced polynomials

Let H(x) be a monic polynomial over a finite field F=GF(q). Denote by Na(n) the number of coefficients in Hn which are equal to an element a∈F, and by G the set of elements a∈F^× such that Na(n)>0 for some n. We study the relationship between the numbers (Na(n))_a∈G and the patterns in the base q representation of n. This enables us to prove that for “most” n's we have Na(n)≈Nb(n), a,b∈G. Considering the case H=x+1, we provide new results on Pascal's triangle modulo a prime. We also provide analogous results for the triangle of Stirling numbers of the first kind.     

Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

A matching M is uniquely restricted in a graph G if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself [M.C. Golumbic, T. Hirst, M. Lewenstein, Uniquely restricted matchings, Algorithmica 31 (2001) 139-154]. G is a König-Egerváry graph provided α(G)+μ(G)=|V(G)| [R.W. Deming, Independence numbers of graphs—an extension of the König-Egerváry theorem, Discrete Math. 27 (1979) 23-33; F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, J. Combin. Theory Ser. B 27 (1979) 228-229], where μ(G) is the size of a maximum matching and α(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G, and we write S∈Ψ(G), if S is a maximum stable set of the subgraph spanned by S∪N(S), where N(S) is the neighborhood of S. Nemhauser and Trotter [Vertex packings: structural properties and algorithms, Math. Programming 8 (1975) 232-248], proved that any S∈Ψ(G) is a subset of a maximum stable set of G. In [V.E. Levit, E. Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Appl. Math. 132 (2003) 163-174] we have proved that for a bipartite graph G,Ψ(G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. In this paper we demonstrate that if G is a triangle-free graph, then Ψ(G) is a greedoid if and only if all its maximum matchings are uniquely restricted and for any S∈Ψ(G), the subgraph spanned by S∪N(S) is a König-Egerváry graph.     

Edge-choosability of planar graphs without adjacent triangles or without 7-cycles

A graph G is edge-L-colorable, if for a given edge assignment L={L(e):e∈E(G)}, there exists a proper edge-coloring ? of G such that ?(e)∈L(e) for all e∈E(G). If G is edge-L-colorable for every edge assignment L with |L(e)|≥k for e∈E(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph with maximum degree Δ(G)≠5 and without adjacent 3-cycles, or with maximum degree Δ(G)≠5,6 and without 7-cycles, then G is edge-(Δ(G)+1)-choosable.     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.     

The complexity of locally injective homomorphisms

A homomorphism f:G→H, from a digraph G to a digraph H, is locally injective if the restriction of f to N⁻(v) is an injective mapping, for each v∈V(G). The problem of deciding whether such an f exists is known as the injective H-colouring problem (INJ-HOM_H). In this paper, we classify the problem INJ-HOM_H as being either a problem in P or a problem that is NP-complete. This is done in the case where H is a reflexive digraph (i.e. H has a loop at every vertex) and in the case where H is an irreflexive tournament. A full classification in the irreflexive case seems hard, and we provide some evidence as to why this may be the case.     

Coloring graphs from random lists of size 2

Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n^1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n^1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n.     

Group-valued continuous functions with the topology of pointwise convergence

Let G be a topological group with the identity element e. Given a space X, we denote by Cp(X,G) the group of all continuous functions from X to G endowed with the topology of pointwise convergence, and we say that X is: (a) G-regular if, for each closed set F⊆X and every point x∈X?F, there exist f∈Cp(X,G) and g∈G?{e} such that f(x)=g and f(F)⊆{e}; (b) G^?-regular provided that there exists g∈G?{e} such that, for each closed set F⊆X and every point x∈X?F, one can find f∈Cp(X,G) with f(x)=g and f(F)⊆{e}. Spaces X and Y are G-equivalent provided that the topological groups Cp(X,G) and Cp(Y,G) are topologically isomorphic.We investigate which topological properties are preserved by G-equivalence, with a special emphasis being placed on characterizing topological properties of X in terms of those of Cp(X,G). Since R-equivalence coincides with l-equivalence, this line of research “includes” major topics of the classical Cp-theory of Arhangel'ski? as a particular case (when G=R).We introduce a new class of TAP groups that contains all groups having no small subgroups (NSS groups). We prove that: (i) for a given NSS group G, a G-regular space X is pseudocompact if and only if Cp(X,G) is TAP, and (ii) for a metrizable NSS group G, a G^?-regular space X is compact if and only if Cp(X,G) is a TAP group of countable tightness. In particular, a Tychonoff space X is pseudocompact (compact) if and only if Cp(X,R) is a TAP group (of countable tightness). Demonstrating the limits of the result in (i), we give an example of a precompact TAP group G and a G-regular countably compact space X such that Cp(X,G) is not TAP.We show that Tychonoff spaces X and Y are T-equivalent if and only if their free precompact Abelian groups are topologically isomorphic, where T stays for the quotient group R/Z. As a corollary, we obtain that T-equivalence implies G-equivalence for every Abelian precompact group G. We establish that T-equivalence preserves the following topological properties: compactness, pseudocompactness, σ-compactness, the property of being a Lindelöf Σ-space, the property of being a compact metrizable space, the (finite) number of connected components, connectedness, total disconnectedness. An example of R-equivalent (that is, l-equivalent) spaces that are not T-equivalent is constructed.     

On the prime power factorization of n!, II

Let p, q be primes and m be a positive integer. For a positive integer n, let ep(n) be the nonnegative integer with pep(n)|n and pep(n)+1?n. The following results are proved: (1) For any positive integer m, any prime p and any ε∈Zm, there are infinitely many positive integers n such that ; (2) For any positive integer m, there exists a constant D(m) such that if ε,δ∈Zm and p, q are two distinct primes with max{p,q}?D(m), then there exist infinitely many positive integers n such that , . Finally we pose four open problems.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.     

Signed star domatic number of a graph

Let G be a simple graph without isolated vertices with vertex set V(G) and edge set E(G). A function f:E(G)?{−1,1} is said to be a signed star dominating function on G if ∑_e∈E(v)f(e)≥1 for every vertex v of G, where E(v)={uv∈E(G)∣u∈N(v)}. A set {f₁,f₂,…,f_d} of signed star dominating functions on G with the property that for each e∈E(G), is called a signed star dominating family (of functions) on G. The maximum number of functions in a signed star dominating family on G is the signed star domatic number of G, denoted by d_SS(G).In this paper we study the properties of the signed star domatic number d_SS(G). In particular, we determine the signed domatic number of some classes of graphs.