Toric complexes and Artin kernels

A simplicial complex L on n vertices determines a subcomplex TL of the n-torus, with fundamental group the right-angled Artin group GL. Given an epimorphism χ:GL→Z, let be the corresponding cover, with fundamental group the Artin kernel Nχ. We compute the cohomology jumping loci of the toric complex TL, as well as the homology groups of with coefficients in a field k, viewed as modules over the group algebra kZ. We give combinatorial conditions for to have trivial Z-action, allowing us to compute the truncated cohomology ring, . We also determine several Lie algebras associated to Artin kernels, under certain triviality assumptions on the monodromy Z-action, and establish the 1-formality of these (not necessarily finitely presentable) groups.     

Rainbowness of cubic plane graphs

The rainbowness, rb(G), of a connected plane graph G is the minimum number k such that any colouring of vertices of the graph G using at least k colours involves a face all vertices of which receive distinct colours. For a connected cubic plane graph G we prove that

     

Linkability in iterated line graphs

We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L³(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number k_G such that for every i?k_G the i-iterated line graph of G is -linked. Since the degree of Lⁱ(G) is even, the result is best possible.     

Homology of artinian and Matlis reflexive modules, I

Let R be a commutative local noetherian ring, and let L and L^′ be R-modules. We investigate the properties of the functors and . For instance, we show the following:

(a)

if L and L^′ are artinian, then is artinian, and is noetherian over the completion ;

(b)

if L is artinian and L^′ is Matlis reflexive, then , , and are Matlis reflexive.

Also, we study the vanishing behavior of these functors, and we include computations demonstrating the sharpness of our results.     

Some relations between rank, chromatic number and energy of graphs

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. Let G be a graph of order n and be the rank of the adjacency matrix of G. In this paper we characterize all graphs with . Among other results we show that apart from a few families of graphs, , where n is the number of vertices of G, and χ(G) are the complement and the chromatic number of G, respectively. Moreover some new lower bounds for E(G) in terms of are given.     

Traceability of line graphs

Brualdi and Shanny [R.A. Brualdi, R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307-314], Clark [L. Clark, On hamitonian line graphs, J. Graph Theory 8 (1984) 303-307] and Veldman [H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239] gave minimum degree conditions of a line graph guaranteeing the line graph to be hamiltonian. In this paper, we investigate the similar conditions guaranteeing a line graph to be traceable. In particular, we show the following result: let G be a simple graph of order n and L(G) its line graph. If n is sufficiently large and, either ; or and G is almost bridgeless, then L(G) is traceable. As a byproduct, we also show that every 2-edge-connected triangle-free simple graph with order at most 9 has a spanning trail. These results are all best possible.     

Note on the energy of regular graphs

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ₁ is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that .     

A spectral radius formula for the Fourier transform on compact groups and applications to random walks

Let G be a compact group, not necessarily abelian, let ? be its unitary dual, and for f∈L¹(G), let fn?f∗?∗f denote n-fold convolution of f with itself and f? the Fourier transform of f. In this paper, we derive the following spectral radius formula

     

The connectivity of a graph and its complement

Let G be a graph with minimum degree δ(G), edge-connectivity λ(G), vertex-connectivity κ(G), and let be the complement of G.In this article we prove that either λ(G)=δ(G) or . In addition, we present the Nordhaus-Gaddum type result . A family of examples will show that this inequality is best possible.     

Lattices generated by join of strongly closed subgraphs in d-bounded distance-regular graphs

Let Γ be a d-bounded distance-regular graph with diameter d?3. Suppose that P(x) is a set of all strongly closed subgraphs containing x and that P(x,i) is a subset of P(x) consisting of all elements of P(x) with diameter i. Let L^′(x,i) be the set generated by all joins of the elements in P(x,i). By ordering L^′(x,i) by inclusion or reverse inclusion, L^′(x,i) is denoted by or . We prove that and are both finite atomic lattices, and give the conditions for them both being geometric lattices. We also give the eigenpolynomial of      

Domination subdivision numbers of trees

A set S of vertices of a graph G=(V,E) is a dominating set if every vertex of V(G)?S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number  is the minimum number of edges that must be subdivided in order to increase the domination number. Velammal showed that for any tree T of order at least 3, . In this paper, we give two characterizations of trees whose domination subdivision number is 3 and a linear algorithm for recognizing them.     

On the Whitehead group of Novikov rings associated to irrational homomorphisms

Given a homomorphism ξ:G→R we show that the natural map from the Whitehead group of G to the Whitehead group of the Novikov ring is surjective. The group is of interest for the simple chain homotopy type of the Novikov complex. It also contains the Latour obstruction for the existence of a nonsingular closed 1-form within a fixed cohomology class ξ∈H¹(M;R), where M is a closed connected smooth manifold.     

On the ratios between packing and domination parameters of a graph

The relationship ρ_L(G)≤ρ(G)≤γ(G) between the lower packing number ρ_L(G), the packing number ρ(G) and the domination number γ(G) of a graph G is well known. In this paper we establish best possible bounds on the ratios of the packing numbers of any (connected) graph to its six domination-related parameters (the lower and upper irredundance numbers ir and IR, the lower and upper independence numbers i and β, and the lower and upper domination numbers γ and Γ). In particular, best possible constants a_θ, b_θ, c_θ and d_θ are found for which the inequalities and hold for any connected graph G and all θ∈{ir,γ,i,β,Γ,IR}. From our work it follows, for example, that and for any connected graph G, and that these inequalities are best possible.     

Characterization of graphs having extremal Randi? indices

The higher Randi? index R_t(G) of a simple graph G is defined as

     

The hamiltonian index of a 2-connected graph

Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp.     

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line of the form [a_i,a_i+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G)≤t+⌈log(n−t)⌉−1 and , where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds.F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, and , where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then and this bound is tight. We also show that if G is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , s≥0, then , where χ(G) is the chromatic number of G.     

Hamilton-connected indices of graphs

Let G be an undirected graph that is neither a path nor a cycle. Clark and Wormald [L.H. Clark, N.C. Wormald, Hamiltonian-like indices of graphs, ARS Combinatoria 15 (1983) 131-148] defined hc(G) to be the least integer m such that the iterated line graph L^m(G) is Hamilton-connected. Let be the diameter of G and k be the length of a longest path whose internal vertices, if any, have degree 2 in G. In this paper, we show that . We also show that κ³(G)≤hc(G)≤κ³(G)+2 where κ³(G) is the least integer m such that L^m(G) is 3-connected. Finally we prove that hc(G)≤|V(G)|−Δ(G)+1. These bounds are all sharp.     

(2,1)-Total labelling of outerplanar graphs

The (2,1)-total labelling number of a graph G is the width of the smallest range of integers that suffices to label the vertices and the edges of G such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper we prove that if G is an outerplanar graph with maximum degree Δ(G), then if Δ(G)?5, or Δ(G)=3 and G is 2-connected, or Δ(G)=4 and G contains no intersecting triangles.     

Decompositions of pseudographs into closed trails of even sizes

We consider a graph L_n, with n even, which is a complete graph with an additional loop at each vertex and minus a 1-factor and we prove that it is edge-disjointly decomposable into closed trails of even lengths greater than four, whenever these lengths sum up to the size of the graph L_n. We also show that this statement remains true if we remove from L_n two loops attached to nonadjacent vertices. Consequently, we improve P. Wittmann’s result on the upper bound of the irregular coloring number c(G) of a 2-regular graph G of size n, by determining that this number is, with a discrepancy of at most one, equal to if all components of G have even orders.