On the list dynamic coloring of graphs

A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex v of degree at least 2, the neighbors of v receive at least two different colors. Assume that is the minimum number k such that for every list assignment of size k to each vertex of G, there is a dynamic coloring of G such that every vertex is colored with a color from its list. In this paper, it is proved that if G is a graph with no component isomorphic to C₅ and Δ(G)≥3, then , where Δ(G) is the maximum degree of G. This generalizes a result due to Lai, Montgomery and Poon which says that under the same assumptions χ₂(G)≤Δ(G)+1. Among other results, we determine , for every natural number n.     

Boxicity of line graphs

The boxicity of a graph H, denoted by , is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper we show that for a line graph G of a multigraph, , where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, . For the d-dimensional hypercube Q_d, we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).     

Complete solution to a conjecture on the Randić index of triangle-free graphs

The Randić index R(G) of a graph G is defined by , where d(u) is the degree of a vertex u in G and the summation extends over all edges uv of G. A conjecture about the Randić index says that for any triangle-free graph G of order n with minimum degree δ≥k≥1, one has , where the equality holds if and only if G=K_k,n−k. In this short note we give a confirmative proof for the conjecture.     

Detecting induced subgraphs

An s-graph is a graph with two kinds of edges: subdivisible edges and real edges. A realisation of an s-graph B is any graph obtained by subdividing subdivisible edges of B into paths of arbitrary length (at least one). Given an s-graph B, we study the decision problem Π_B whose instance is a graph G and question is “Does G contain a realisation of B as an induced subgraph?”. For several B’s, the complexity of Π_B is known and here we give the complexity for several more.Our NP-completeness proofs for Π_B’s rely on the NP-completeness proof of the following problem. Let be a set of graphs and d be an integer. Let be the problem whose instance is (G,x,y) where G is a graph whose maximum degree is at most d, with no induced subgraph in and x,yV(G) are two non-adjacent vertices of degree 2. The question is “Does G contain an induced cycle passing through x,y?”. Among several results, we prove that is NP-complete. We give a simple criterion on a connected graph H to decide whether is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour.     

Engel graph associated with a group

Let G be a non-Engel group and let L(G) be the set of all left Engel elements of G. Associate with G a graph as follows: Take G L(G) as vertices of and join two distinct vertices x and y whenever [x,_ky]≠1 and [y,_kx]≠1 for all positive integers k. We call , the Engel graph of G. In this paper we study the graph theoretical properties of .     

Bounds relating the weakly connected domination number to the total domination number and the matching number

Let G=(V,E) be a connected graph. A dominating set S of G is a weakly connected dominating set of G if the subgraph (V,E∩(S×V)) of G with vertex set V that consists of all edges of G incident with at least one vertex of S is connected. The minimum cardinality of a weakly connected dominating set of G is the weakly connected domination number, denoted . A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. In this paper, we show that . Properties of connected graphs that achieve equality in these bounds are presented. We characterize bipartite graphs as well as the family of graphs of large girth that achieve equality in the lower bound, and we characterize the trees achieving equality in the upper bound. The number of edges in a maximum matching of G is called the matching number of G, denoted α^′(G). We also establish that , and show that for every tree T.     

A note on the signed edge domination number in graphs

Let G=(V(G),E(G)) be a graph. A function f:E(G)→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑_e^′N[e]f(e^′)≥1 for every eE(G). The signed edge domination number of G is defined as is a SEDF of G}. Xu [Baogen Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics 154 (2006) 1541–1546] researched on the edge domination in graphs and proved that for any graph G of order n(n≥4). In the article, he conjectured that: For any 2-connected graph G of order n(n≥2), . In this note, we present some counterexamples to the above conjecture and prove that there exists a family of k-connected graphs G_m,k with .     

Linear choosability of sparse graphs

A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , of sparse graphs. The maximum average degree of a graph G, denoted mad(G), is the maximum of the average degrees of all subgraphs of G. It is clear that any graph G with maximum degree Δ(G) satisfies . In this paper, we prove the following results: (1) if and Δ(G)≥3, then , and we give an infinite family of examples to show that this result is best possible; (2) if and Δ(G)≥9, then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if G is planar and has girth at least 5, then .     

A new upper bound for the total vertex irregularity strength of graphs

We investigate the following modification of the well-known irregularity strength of graphs. Given a total weighting w of a graph G=(V,E) with elements of a set {1,2,…,s}, denote wt_G(v)=∑_evw(e)+w(v) for each vV. The smallest s for which exists such a weighting with wt_G(u)≠wt_G(v) whenever u and v are distinct vertices of G is called the total vertex irregularity strength of this graph, and is denoted by . We prove that for each graph of order n and with minimum degree δ>0.     

Uniform asymptotic approximations for incomplete Riemann Zeta functions

An incomplete Riemann Zeta function Z₁(α,x) is examined, along with a complementary incomplete Riemann Zeta function Z₂(α,x). These functions are defined by and Z₂(α,x)=ζ(α)-Z₁(α,x), where ζ(α) is the classical Riemann Zeta function. Z₁(α,x) has the property that for and α≠1. The asymptotic behaviour of Z₁(α,x) and Z₂(α,x) is studied for the case fixed and , and using Liouville–Green (WKBJ) analysis, asymptotic approximations are obtained, complete with explicit error bounds, which are uniformly valid for 0x<∞.     

Covering line graphs with equivalence relations

An equivalence graph is a disjoint union of cliques, and the equivalence number of a graph G is the minimum number of equivalence subgraphs needed to cover the edges of G. We consider the equivalence number of a line graph, giving improved upper and lower bounds: . This disproves a recent conjecture that is at most three for triangle-free G; indeed it can be arbitrarily large.To bound we bound the closely related invariant σ(G), which is the minimum number of orientations of G such that for any two edges e,f incident to some vertex v, both e and f are oriented out of v in some orientation. When G is triangle-free, . We prove that even when G is triangle-free, it is NP-complete to decide whether or not σ(G)≤3.     

Rigid realizations of graphs on small grids

A framework (G,p) is a straight line realization of a graph G=(V,E) in , given by a map . We prove that if (G,p) is an infinitesimally rigid framework then there is an infinitesimally rigid framework (G,q) for which the points q(v), vV(G), are distinct points of the k×k grid, where . We also show that such a framework on G can be constructed in O(|V|³) time.     

On the graph of a function over a prime field whose small powers have bounded degree

Let f be a function from a finite field with a prime number p of elements, to . In this article we consider those functions f(X) for which there is a positive integer with the property that f(X)ⁱ, when considered as an element of , has degree at most p−2−n+i, for all i=1,…,n. We prove that every line is incident with at most t−1 points of the graph of f, or at least n+4−t points, where t is a positive integer satisfying n>(p−1)/t+t−3 if n is even and n>(p−3)/t+t−2 if n is odd. With the additional hypothesis that there are t−1 lines that are incident with at least t points of the graph of f, we prove that the graph of f is contained in these t−1 lines. We conjecture that the graph of f is contained in an algebraic curve of degree t−1 and prove the conjecture for t=2 and t=3. These results apply to functions that determine less than directions. In particular, the proof of the conjecture for t=2 and t=3 gives new proofs of the result of Lovász and Schrijver [L. Lovász, A. Schrijver, Remarks on a theorem of Rédei, Studia Sci. Math. Hungar. 16 (1981) 449–454] and the result in [A. Gács, On a generalization of Rédei’s theorem, Combinatorica 23 (2003) 585–598] respectively, which classify all functions which determine at most 2(p−1)/3 directions.     

The energy of unitary cayley graphs

A graph G of order n is called hyperenergetic if E(G)>2n-2, where E(G) denotes the energy of G. The unitary Cayley graph X_n has vertex set Z_n={0,1,2,…,n-1} and vertices a and b are adjacent, if gcd(a-b,n)=1. These graphs have integral spectrum and play an important role in modeling quantum spin networks supporting the perfect state transfer. We show that the unitary Cayley graph X_n is hyperenergetic if and only if n has at least two prime factors greater than 2 or at least three distinct prime factors. In addition, we calculate the energy of the complement of unitary Cayley graph and prove that is hyperenergetic if and only if n has at least two distinct prime factors and n≠2p, where p is a prime number. By extending this approach, for every fixed , we construct families of k hyperenergetic non-cospectral integral circulant n-vertex graphs with equal energy.     

Primitive permutation groups with a regular subgroup

This paper starts the classification of the primitive permutation groups (G,Ω) such that G contains a regular subgroup X. We determine all the triples (G,Ω,X) with soc(G) an alternating, or a sporadic or an exceptional group of Lie type. Further, we construct all the examples (G,Ω,X) with G a classical group which are known to us. Our particular interest is in the 8-dimensional orthogonal groups of Witt index 4. We determine all the triples (G,Ω,X) with . In order to obtain all these triples, we also study the almost simple groups G with GPΩ_2n+1(q). The case GU_n(q) is started in this paper and finished in [B. Baumeister, Primitive permutation groups of unitary type with a regular subgroup, Bull. Belg. Math. Soc. 112 (5) (2006) 657–673]. A group X is called a Burnside-group (or short a B-group) if each primitive permutation group which contains a regular subgroup isomorphic to X is necessarily 2-transitive. In the end of the paper we discuss B-groups.     

Upper bounds on the linear chromatic number of a graph

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Δ(G). In this paper we prove the following results: (1) ; (2) if Δ(G)≤4; (3) if Δ(G)≤5; (4) if G is planar and Δ(G)≥52.     

Lipschitz regularity for scalar minimizers of autonomous simple integrals

We prove Lipschitz regularity for a minimizer of the integral , defined on the class of the AC functions having x(a)=A and x(b)=B. The Lagrangian may have L(s,) nonconvex (except at ξ=0), while may be non-lsc, measurability sufficing for ξ≠0 provided, e.g., L^**() is lsc at (s,0) s. The essential hypothesis (to yield Lipschitz minimizers) turns out to be local boundedness of the quotient φ/ρ() (and not of L^**() itself, as usual), where φ(s)+ρ(s)h(ξ) approximates the bipolar L^**(s,ξ) in an adequate sense. Moreover, an example of infinite Lavrentiev gap with a scalar 1-dim autonomous (but locally unbounded) lsc Lagrangian is presented.     

On the eccentric connectivity index of a graph

If G is a connected graph with vertex set V, then the eccentric connectivity index of G, ξ^C(G), is defined as where is the degree of a vertex v and is its eccentricity. We obtain an exact lower bound on ξ^C(G) in terms of order, and show that this bound is sharp. An asymptotically sharp upper bound is also derived. In addition, for trees of given order, when the diameter is also prescribed, precise upper and lower bounds are provided.     

Some rigidity results for non-commutative Bernoulli shifts

We introduce the outer conjugacy invariants , for cocycle actions σ of discrete groups G on type II₁ factors N, as the set of real numbers t>0 for which the amplification σ^t of σ can be perturbed to an action, respectively, to a weakly mixing action. We calculate explicitly and the fundamental group of σ, , in the case G has infinite normal subgroups with the relative property (T) (e.g., when G itself has the property (T) of Kazhdan) and σ is an action of G on the hyperfinite II₁ factor by Connes–Størmer Bernoulli shifts of weights {t_i}_i. Thus, and coincide with the multiplicative subgroup S of generated by the ratios {t_i/t_j}_i,j, while if S={1} (i.e. when all weights are equal), and otherwise. In fact, we calculate all the “1-cohomology picture” of σ^t,t>0, and classify the actions (σ,G) in terms of their weights {t_i}_i. In particular, we show that any 1-cocycle for (σ,G) vanishes, modulo scalars, and that two such actions are cocycle conjugate iff they are conjugate. Also, any cocycle action obtained by reducing a Bernoulli action of a group G as above on to the algebra pNp, for p a projection in N, p≠0,1, cannot be perturbed to a genuine action.     

Common transversals in the plane: The fractional perspective

A fresh look is taken at the fractional Helly theorem for line transversals to families of convex sets in the plane. This theorem was first proved in 1980 by Katchalski and Liu [M. Katchalski, A. Liu, Symmetric twins and common transversals, Pacific J. Math. 86 (1980) 513–515]. It asserts that for every integer k≥3, there exists a real number ρ(k)(0,1) such that the following holds: If is a family of n compact convex sets in the plane, and any k or fewer members of have a line transversal, then some subfamily of of size at least has a line transversal. A lower bound on ρ(k) is obtained which is stronger than the one obtained in [M. Katchalski, A. Liu, Symmetric twins and common transversals, Pacific J. Math. 86 (1980) 513–515]. Also, examples are given to show that a conjecture of Katchalski concerning the value of ρ(3), if true, is the best possible.