Spectral analysis of the affine graph over the finite ring

We apply two methods to the block diagonalization of the adjacency matrix of the Cayley graph defined on the affine group. The affine group will be defined over the finite ring Z/pⁿZ. The method of irreducible representations will allow us to find nontrivial eigenvalue bounds for two different graphs. One of these bounds will result in a family of Ramanujan graphs. The method of covering graphs will be used to block diagonalize the affine graphs using a Galois group of graph automorphisms. In addition, we will demonstrate the method of covering graphs on a generalized version of the graphs of Lubotzky et al. [A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261-277].     

Self-clique Helly circular-arc graphs

A clique in a graph is a complete subgraph maximal under inclusion. The clique graph of a graph is the intersection graph of its cliques. A graph is self-clique when it is isomorphic to its clique graph. A circular-arc graph is the intersection graph of a family of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. In this note, we describe all the self-clique Helly circular-arc graphs.     

Every minor-closed property of sparse graphs is testable

Suppose G is a graph of bounded degree d, and one needs to remove ?n of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of G is far from the statistics of local neighborhoods around vertices of any planar graph G^′. In fact, a similar result is proved for any minor-closed property of bounded degree graphs.The main motivation of the above result comes from theoretical computer-science. Using our main result we infer that for any minor-closed property P, there is a constant time algorithm for detecting if a graph is “far” from satisfying P. This, in particular, answers an open problem of Goldreich and Ron [STOC 1997] [20], who asked if such an algorithm exists when P is the graph property of being planar. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.     

On a conjecture of Brouwer involving the connectivity of strongly regular graphs

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O⁺(2r,2) and from the elliptic quadrics O⁻(2r,2) over the field F₂, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.     

Quasi-injective dimension

Following our previous work about quasi-projective dimension [11], in this paper, we introduce quasi-injective dimension as a generalization of injective dimension. We recover several well-known results about injective and Gorenstein-injective dimensions in the context of quasi-injective dimension such as the following. (a) If the quasi-injective dimension of a finitely generated module M over a local ring R is finite, then it is equal to the depth of R. (b) If there exists a finitely generated module of finite quasi-injective dimension and maximal Krull dimension, then R is Cohen-Macaulay. (c) If there exists a nonzero finitely generated module with finite projective dimension and finite quasi-injective dimension, then R is Gorenstein. (d) Over a Gorenstein local ring, the quasi-injective dimension of a finitely generated module is finite if and only if its quasi-projective dimension is finite.     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

Algorithms for clique-independent sets on subclasses of circular-arc graphs

A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n²). These algorithms suppose that an HCA model of the graph is given.     

Construction of some countable 1-arc-transitive bipartite graphs

We generalize earlier work which gave a method of construction for bipartite graphs which are obtained as the set of maximal or minimal elements of a certain cycle-free partial order. The method is extended here to produce a 1-arc-transitive bipartite graph in a ‘free’ way, starting with any partial order with greatest and least element and with instructions on its points about how they will ramify in the extension. A key feature of our work is the interplay between properties of the initial partial order, the extended partial order, and the bipartite graph which results. We also extend the earlier work by giving a complete characterization of all 2-CS-transitive cycle-free partial orders. In addition, we discuss the completeness of the constructed partial orders, in the sense of Dedekind and MacNeille, and remark that the bipartite graph constructed can only be 2-arc-transitive in the cycle-free case.     

Minimal comparability completions of arbitrary graphs

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Π for which Π completion of arbitrary graphs can be achieved through such a vertex incremental approach.     

An extension of regular supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we consider an extension of regular supermagic graphs and apply it to some constructions of supermagic graphs. Using the extension we prove that for any graph G there is a supermagic regular graph which contains an induced subgraph isomorphic to G.     

Observable graphs

An edge-colored directed graph is observable if an agent that moves along its edges from node to node is able to determine his position in the graph after a sufficiently long observation of the edge colors, and without accessing any information about the traversed nodes. When the agent is able to determine his position only from time to time, the graph is said to be partly observable. Observability in graphs is desirable in situations where autonomous agents are moving on a network and they want to localize themselves with limited information. In this paper, we completely characterize observable and partly observable graphs and show how these concepts relate to other concepts in the literature. Based on these characterizations, we provide polynomial time algorithms to decide observability, to decide partial observability, and to compute the minimal number of observations necessary for finding the position of an agent. In particular we prove that in the worst case this minimal number of observations increases quadratically with the number of nodes in the graph. We then consider the more difficult question of assigning colors to a graph so as to make it observable and we prove that two different versions of this problem are NP-complete.     

Eulerian detachments with local edge-connectivity

For a graph G, a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph G by applying detachment operations at several vertices is called a detachment of graph G. While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless.     

Collapsible biclaw-free graphs

A graph is called biclaw-free if it has no biclaw as an induced subgraph. In this note, we prove that if G is a connected bipartite biclaw-free graph with δ(G)?5, then G is collapsible, and of course supereulerian. This bound is best possible.     

Ring geometries,two-weight codes,and strongly regular graphs

It is known that a projective linear two-weight code C over a finite field corresponds both to a set of points in a projective space over that meets every hyperplane in either a or b points for some integers a < b, and to a strongly regular graph whose vertices may be identified with the codewords of C. Here we extend this classical result to the case of a ring-linear code with exactly two nonzero homogeneous weights and sets of points in an associated projective ring geometry. We will introduce regular projective two-weight codes over finite Frobenius rings, we will show that such a code gives rise to a strongly regular graph, and we will give some constructions of two-weight codes using ring geometries. All these examples yield infinite families of strongly regular graphs with non-trivial parameters.      

Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs.     

Finite rings in which commutativity is transitive

A ring is called commutative transitive if commutativity is a transitive relation on its nonzero elements. Likewise, it is weakly commutative transitive (wCT) if commutativity is a transitive relation on its noncentral elements. The main topic of this paper is to describe the structure of finite wCT rings. It is shown that every such ring is a direct sum of an indecomposable noncommutative wCT ring of prime power order, and a commutative ring. Furthermore, finite indecomposable wCT rings are either two-by-two matrices over fields, local rings, or basic rings with two maximal ideals. We characterize finite local rings as generalized skew polynomial rings over coefficient Galois rings; the associated automorphisms of the Galois ring give rise to a signature of the local ring. These are then used to further describe the structure of finite local and wCT basic rings.     

Semisymmetric graphs from polytopes

Every finite, self-dual, regular (or chiral) 4-polytope of type {3,q,3} has a trivalent 3-transitive (or 2-transitive) medial layer graph. Here, by dropping self-duality, we obtain a construction for semisymmetric trivalent graphs (which are edge- but not vertex-transitive). In particular, the Gray graph arises as the medial layer graph of a certain universal locally toroidal regular 4-polytope.     

On crossing numbers of geometric proximity graphs

Let P be a set of n points in the plane. A geometric proximity graph on P is a graph where two points are connected by a straight-line segment if they satisfy some prescribed proximity rule. We consider four classes of higher order proximity graphs, namely, the k-nearest neighbor graph, the k-relative neighborhood graph, the k-Gabriel graph and the k-Delaunay graph. For k=0 (k=1 in the case of the k-nearest neighbor graph) these graphs are plane, but for higher values of k in general they contain crossings. In this paper, we provide lower and upper bounds on their minimum and maximum number of crossings. We give general bounds and we also study particular cases that are especially interesting from the viewpoint of applications. These cases include the 1-Delaunay graph and the k-nearest neighbor graph for small values of k.     

Embedding arbitrary finite simple graphs into small strongly regular graphs

It is well known that any finite simple graph Γ is an induced subgraph of some exponentially larger strongly regular graph Γ (e.g., [2, 8]). No general polynomial‐size construction has been known. For a given finite simple graph Γ on υ vertices, we present a construction of a strongly regular graph Γ on O(υ⁴) vertices that contains Γ as its induced subgraph. A discussion is included of the size of the smallest possible strongly regular graph with this property. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 1–8, 2000