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 .     

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.     

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

All-derivable points in continuous nest algebras

Let be an operator algebra on a Hilbert space. We say that an element is an all-derivable point of for the strong operator topology if every strong operator topology continuous derivable linear mapping φ at G (i.e. φ(ST)=φ(S)T+Sφ(T) for any with ST=G) is a derivation. Let be a continuous nest on a complex and separable Hilbert space H. We show in this paper that every orthogonal projection operator P(M) () is an all-derivable point of for the strong operator topology.     

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.     

A proof of a conjecture on the Randić index of graphs with given girth

The Randić index R(G) of a graph G is defined by , where is the degree of a vertex u in G and the summation extends over all edges uv of G. Aouchiche, Hansen and Zheng proposed the following conjecture: For any connected graph on n≥3 vertices with Randić index R and girth g,

with equalities if and only if . This paper is devoted to giving a confirmative proof to this conjecture.     

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.     

Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies

The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function such that |Λ(u)−Λ(v)|2, when u,v are neighbors in G, and |Λ(u)−Λ(v)|1 when the distance of u,v in G is two. The discrete number of frequencies used is called order and the range of frequencies used, span. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span (min span RCP) or the order (min order RCP).In this paper, we deal with an interesting, yet not examined until now, variation of the radiocoloring problem: that of satisfying frequency assignment requests which exhibit some periodic behavior. In this case, the interference graph (modelling interference between transmitters) is some (infinite) periodic graph. Infinite periodic graphs usually model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they can model very large networks produced by the repetition of a small graph.A periodic graph G is defined by an infinite two-way sequence of repetitions of the same finite graph G_i(V_i,E_i). The edge set of G is derived by connecting the vertices of each iteration G_i to some of the vertices of the next iteration G_i+1, the same for all G_i. We focus on planar periodic graphs, because in many cases real networks are planar and also because of their independent mathematical interest.We give two basic results:

• We prove that the min span RCP is PSPACE-complete for periodic planar graphs.

• We provide an O(n(Δ(G_i)+σ)) time algorithm (where|V_i|=n, Δ(G_i) is the maximum degree of the graph G_i and σ is the number of edges connecting each G_i to G_i+1), which obtains a radiocoloring of a periodic planar graph G that approximates the minimum span within a ratio which tends to as Δ(G_i)+σ tends to infinity.

We remark that, any approximation algorithm for the min span RCP of a finite planar graph G, that achieves a span of at most αΔ(G)+constant, for any α and where Δ(G) is the maximum degree of G, can be used as a subroutine in our algorithm to produce an approximation for min span RCP of asymptotic ratio α for periodic planar graphs.

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.     

The noncentral Wishart as an exponential family, and its moments

While the noncentral Wishart distribution is generally introduced as the distribution of the random symmetric matrix where Y₁,…,Y_n are independent Gaussian rows in with the same covariance, the present paper starts from a slightly more general definition, following the extension of the chi-square distribution to the gamma distribution. We denote by γ(p,a;σ) this general noncentral Wishart distribution: the real number p is called the shape parameter, the positive definite matrix σ of order k is called the shape parameter and the semi-positive definite matrix a of order k is such that the matrix ω=σaσ is called the noncentrality parameter. This paper considers three problems: the derivation of an explicit formula for the expectation of when Xγ(p,a,σ) and h₁,…,h_m are arbitrary symmetric matrices of order k, the estimation of the parameters (a,σ) by a method different from that of Alam and Mitra [K. Alam, A. Mitra, On estimated the scale and noncentrality matrices of a Wishart distribution, Sankhyā, Series B 52 (1990) 133–143] and the determination of the set of acceptable p’s as already done by Gindikin and Shanbag for the ordinary Wishart distribution γ(p,0,σ).     

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.