Integral circulant graphs of prime power order with maximal energy

The energy of a graph is the sum of the moduli of the eigenvalues of its adjacency matrix. We study the energy of integral circulant graphs, also called gcd graphs, which can be characterized by their vertex count n and a set D of divisors of n in such a way that they have vertex set Z_n and edge set {{a,b}:a,b∈Z_n,gcd(a-b,n)∈D}. Using tools from convex optimization, we analyze the maximal energy among all integral circulant graphs of prime power order p^s and varying divisor sets D. Our main result states that this maximal energy approximately lies between s(p-1)p^s-1 and twice this value. We construct suitable divisor sets for which the energy lies in this interval. We also characterize hyperenergetic integral circulant graphs of prime power order and exhibit an interesting topological property of their divisor sets.     

Transversal numbers of translates of a convex body

Let F be a family of translates of a fixed convex set M in Rⁿ. Let τ(F) and ν(F) denote the transversal number and the independence number of F, respectively. We show that ν(F)?τ(F)?8ν(F)-5 for n=2 and τ(F)?2^n-1nⁿν(F) for n?3. Furthermore, if M is centrally symmetric convex body in the plane, then ν(F)?τ(F)?6ν(F)-3.     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

On almost self-complementary graphs

A graph is called almost self-complementary if it is isomorphic to one of its almost complements X^c-I, where X^c denotes the complement of X and I a perfect matching (1-factor) in X^c. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23-44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.     

Perfect state transfer in integral circulant graphs of non-square-free order

This paper provides further results on the perfect state transfer in integral circulant graphs (ICG graphs). The non-existence of PST is proved for several classes of ICG graphs containing an isolated divisor d₀, i.e. the divisor which is relatively prime to all other divisors from d∈D?{d₀}. The same result is obtained for classes of integral circulant graphs having the NSF property (i.e. each n/d is square-free, for every d∈D). A direct corollary of these results is the characterization of ICG graphs with two divisors, which have PST. A similar characterization is obtained for ICG graphs where each two divisors are relatively prime. Finally, it is shown that ICG graphs with the number of vertices n=2p² do not have PST.     

Infinitely many pairs of cospectral integral regular graphs

A graph G is called integral if all the eigenvalues of the adjacency matrix A(G) of G are integers. In this paper, the graphs G ₄(a, b) and G ₅(a, b) with 2a+6b vertices are defined. We give their characteristic polynomials from matrix theory and prove that the (n+2)-regular graphs G ₄(n, n+2) and G ₅(n, n+2) are a pair of non-isomorphic connected cospectral integral regular graphs for any positive integer n.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Note on unicyclic graphs with given number of pendent vertices and minimal energy

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let G(n,p) denote the set of unicyclic graphs with n vertices and p pendent vertices. In [H. Hua, M. Wang, Unicyclic graphs with given number of pendent vertices and minimal energy, Linear Algebra Appl. 426 (2007) 478-489], Hua and Wang discussed the graphs that have minimal energy in G(n,p), and determined the minimal-energy graphs among almost all different cases of n and p. In their work, certain case of the values was left as an open problem in which the minimal-energy species have to be chosen in two candidate graphs, but cannot be determined by comparing of the corresponding coefficients of their characteristic polynomials. This paper aims at solving the problem completely, by using the well-known Coulson integral formula.     

An implicit representation of chordal comparability graphs in linear time

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n²).     

Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is Ω(n^0.694), and the circumference of a 3-connected claw-free graph is Ω(n^0.121). We generalize and improve the first result by showing that every 3-edge-connected graph with m edges has an Eulerian subgraph with Ω(m^0.753) edges. We use this result together with the Ryjá?ek closure operation to improve the lower bound on the circumference of a 3-connected claw-free graph to Ω(n^0.753). Our proofs imply polynomial time algorithms for finding large Eulerian subgraphs of 3-edge-connected graphs and long cycles in 3-connected claw-free graphs.     

Laplacian integral graphs in S(a, b)

Let G_n,m be the family of graphs with n vertices and m edges, when n and m are previously given. It is well-known that there is a subset of G_n,m constituted by graphs G such that the vertex connectivity, the edge connectivity, and the minimum degree are all equal. In this paper, S(a, b)-classes of connected (a, b)-linear graphs with n vertices and m edges are described, where m is given as a function of a,b∈N/2. Some of them have extremal graphs for which the equalities above are extended to algebraic connectivity. These graphs are Laplacian integral although they are not threshold graphs. However, we do build threshold graphs in S(a, b).     

Non-cover generalized Mycielski, Kneser, and Schrijver graphs

A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs M_m(C_2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number.     

Closure, stability and iterated line graphs with a 2-factor

We consider 2-factors with a bounded number of components in the n-times iterated line graph Lⁿ(G). We first give a characterization of graph G such that Lⁿ(G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Lⁿ(G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjá?ek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; Z. Ryjá?ek, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117; L. Xiong, Z. Ryjá?ek, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115].     

Distance spectra and distance energy of integral circulant graphs

The distance energy of a graph G is a recently developed energy-type invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix of G. There was a vast research for the pairs and families of non-cospectral graphs having equal distance energy, and most of these constructions were based on the join of graphs. A graph is called circulant if it is Cayley graph on the circulant group, i.e. its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. In this paper, we characterize the distance spectra of integral circulant graphs and prove that these graphs have integral eigenvalues of distance matrix D. Furthermore, we calculate the distance spectra and distance energy of unitary Cayley graphs. In conclusion, we present two families of pairs (G₁,G₂) of integral circulant graphs with equal distance energy - in the first family G₁ is subgraph of G₂, while in the second family the diameter of both graphs is three.     

Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

Codes associated with circulant graphs and permutation decoding

Binary codes that can be obtained from designs associated with circulant graphs G(n, S) are studied. The parameters of the codes and the information sets are obtained. PD-sets for full-error correction are found for certain values of n.     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.     

Graphs with integral spectrum

It is shown that only a fraction of 2^-Ω(n) of the graphs on n vertices have an integral spectrum. Although there are several explicit constructions of such graphs, no upper bound for their number has been known. Graphs of this type play an important role in quantum networks supporting the so-called perfect state transfer.