On the computational complexity of partial covers of Theta graphs

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.     

Spectral results on graphs with regularity constraints

Graphs with (k, τ)-regular sets and equitable partitions are examples of graphs with regularity constraints. A (k, τ)-regular set of a graph G is a subset of vertices S ⊆ V(G) inducing a k-regular subgraph and such that each vertex not in S has τ neighbors in S. The existence of such structures in a graph provides some information about the eigenvalues and eigenvectors of its adjacency matrix. For example, if a graph G has a (k₁, τ₁)-regular set S₁ and a (k₂, τ₂)-regular set S₂ such that k₁ − τ₁ = k₂ − τ₂ = λ, then λ is an eigenvalue of G with a certain eigenvector. Additionally, considering primitive strongly regular graphs, a necessary and sufficient condition for a particular subset of vertices to be (k, τ)-regular is introduced. Another example comes from the existence of an equitable partition in a graph. If a graph G, has an equitable partition π then its line graph, L(G), also has an equitable partition, , induced by π, and the adjacency matrix of the quotient graph is obtained from the adjacency matrix of G/π.     

Clique-width of graphs defined by one-vertex extensions

Let G be a graph and u be a vertex of G. We consider the following operation: add a new vertex v such that v does not distinguish any two vertices which are not distinguished by u. We call this operation a one-vertex extension. Adding a true twin, a false twin or a pendant vertex are cases of one-vertex extensions. Here we are interested in graph classes defined by a subset of allowed one-vertex extension. Examples are trees, cographs and distance-hereditary graphs. We give a complete classification of theses classes with respect to their clique-width. We also introduce a new graph parameter called the modular-width, and we give a relation with the clique-width.     

Multicyclic treelike reflexive graphs

A simple graph is reflexive if its second largest eigenvalue does not exceed 2. A graph is treelike (sometimes also called a cactus) if all its cycles (circuits) are mutually edge-disjoint. In a lot of cases one can establish whether a given graph is reflexive by identifying and removing a single cut-vertex (Theorem 1). In this paper we prove that, if this theorem cannot be applied to a connected treelike reflexive graph G and if all its cycles do not have a common vertex (do not form a bundle), such a graph has at most five cycles (Theorem 2). On the same conditions, in Theorem 3 we find all maximal treelike reflexive graphs with four and five cycles.     

A case study of cracks in the scientific enterprise: Reinvention of information‐theoretic measures for graphs

This article calls attention to flaws in the scientific enterprise, providing a case study of the lack of professionalism in published journal articles in a particular area of research, namely, network complexity. By offering details of a special case of poor scholarship, which is very likely indicative of a broader problem, the authors hope to stimulate editors and referees to greater vigilance, and to strengthen authors' resolve to take their professional responsibilities more seriously. © 2014 Wiley Periodicals, Inc. Complexity 21: 10–14, 2016     

The computational strength of matchings in countable graphs

In a 1977 paper, Steffens identified an elegant criterion for determining when a countable graph has a perfect matching. In this paper, we will investigate the proof-theoretic strength of this result and related theorems. We show that a number of natural variants of these theorems are equivalent, or closely related, to the “big five” subsystems of reverse mathematics.The results of this paper explore the relationship between graph theory and logic by showing the way in which specific changes to a single graph-theoretic principle impact the corresponding proof-theoretic strength. Taken together, the results and questions of this paper suggest that the existence of matchings in countable graphs provides a rich context for understanding reverse mathematics more broadly.     

On cover-structure graphs

Motivated by a problem in communication complexity, we study cover-structure graphs (cs-graphs), defined as intersection graphs of maximal monochromatic rectangles in a matrix. We show that not every graph is a cs-graph. Especially, squares and odd holes are not cs-graphs.It is natural to look at graphs (beautiful graphs) having the property that each induced subgraph is a cs-graph. They form a new class of Berge graphs. We make progress towards their characterization by showing that every square-free bipartite graph is beautiful, and that beautiful line graphs of square-free bipartite graphs are just Path-or-Even-Cycle-of-Cliques graphs.     

Primitive decompositions of Johnson graphs

A transitive decomposition of a graph is a partition of the edge set together with a group of automorphisms which transitively permutes the parts. In this paper we determine all transitive decompositions of the Johnson graphs such that the group preserving the partition is arc-transitive and acts primitively on the parts.     

Twins of rayless graphs

Two non-isomorphic graphs are twins if each is isomorphic to a subgraph of the other. We prove that a rayless graph has either infinitely many twins or none.     

Hamilton decompositions of graphs with primitive complements

A k-factor of a graph is a k-regular spanning subgraph. A Hamilton cycle is a connected 2-factor. A graph G is said to be primitive if it contains no k-factor with 1≤k<Δ(G). A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each of which induces a Hamilton cycle. In this paper, by using the amalgamation technique, we find necessary and sufficient conditions for the existence of a 2x-regular graph G on n vertices which:

1.

has a Hamilton decomposition, and

2.

has a complement in K_n that is primitive.

This extends the conditions studied by Hoffman, Rodger, and Rosa [D.G. Hoffman, C.A. Rodger, A. Rosa, Maximal sets of 2-factors and Hamiltonian cycles, J. Combin. Theory Ser. B 57 (1) (1993) 69-76] who considered maximal sets of Hamilton cycles and 2-factors. It also sheds light on construction approaches to the Hamilton-Waterloo problem.     

Bisections of graphs

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. In this paper, motivated by several questions and conjectures of Bollobás and Scott, we study maximum bisections of graphs. First, we extend the classical Edwards bound on maximum cuts to bisections. A simple corollary of our result implies that every graph on n vertices and m   edges with no isolated vertices, and maximum degree at most n/3+1$n/3+1$, admits a bisection of size at least m/2+n/6$m/2+n/6$. Then using the tools that we developed to extend Edwards?s bound, we prove a judicious bisection result which states that graphs with large minimum degree have a bisection in which both parts span relatively few edges. A special case of this general theorem answers a conjecture of Bollobás and Scott, and shows that every graph on n vertices and m   edges of minimum degree at least 2 admits a bisection in which the number of edges in each part is at most (1/3+o(1))m$(1/3+o(1))m$. We also present several other results on bisections of graphs.     

A characterization of block graphs

A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let N_e(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uv∈E(G), if x∈N_e(u) and y∈N_e(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22].     

Symmetrical path-cycle covers of a graph and polygonal graphs

A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We introduce a method for constructing near-polygonal graphs with 2-arc transitive automorphism groups. As special cases, we obtain several new infinite families of polygonal graphs.     

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.