The nucleus of a point determining graph

A graph is point determining if distinct points have distinct neighborhoods. In this paper we investigate the nucleus G⁰={υ?G:G–υ is point determining} of a point determining graph G. In particular, we characterize those graphs that are the nucleus of some connected point determining graph.     

On 1-factors of point determining graphs

A graph G is said to be point determining if and only if distinct points of G have distinct neighborhoods. For such a graph G, the nucleus is defined to be the set G″ consisting of all points ν of G for which G-ν is a point determining graph.In [4], Summer exhibited several families of graphs H such that if G⁰ = H, for some point determining graph G, then G has a 1-factor. In this paper, we extend this class of graphs.     

Line-critical point determining and point distinguishing graphs

Sumner defined a graph to be point determining if and only if distinct points have distinct neighborhoods and he has characterized connected line-critical point determining graphs. Here a short alternate proof of his characterization is provided and arbitrary line-critical point determining graphs are then characterized. Next line-critical point distinguishing graphs are considered; a graph is point distinguishing if and only if it is the complement of a point determining graph. Finally, line-critical graphs that are both point determining and point distinguishing are characterized.     

Point determination in graphs

A point determining graph is defined to be a graph in which distinct nonadjacent points have distinct neighborhoods. Those graphs which are critical with respect to this property are studied. We show that a graph is complete if and only if it is connected, point determining, but fails to remain point determining upon the removal of any edge. We also show that every connected, point determining graph contains at least two points, the removal of either of which will result again in a point determining graph. Graphs which are point determining and contain exactly two such points are shown to have the property that every point is adjacent to exactly one of these two points.     

An upper bound on the size of a largest clique in a graph

A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point-determining graph is the set G^O of all vertices, v, such that G–v is point determining. In this paper we show that the size, ω(G), of a maximum clique in G satisfies ω(G) ? 2|π (G)^O|, where π(G) (the point determinant of G) is obtained from G by identifying vertices which have the same neighborhood.     

On realizations of point determining graphs, and obstructions to full homomorphisms

A graph is point determining if distinct vertices have distinct neighbourhoods. A realization of a point determining graph H is a point determining graph G such that each vertex-removed subgraph G-x which is point determining, is isomorphic to H. We study the fine structure of point determining graphs, and conclude that every point determining graph has at most two realizations.A full homomorphism of a graph G to a graph H is a vertex mapping f such that for distinct vertices u and v of G, we have uv an edge of G if and only if f(u)f(v) is an edge of H. For a fixed graph H, a full H-colouring of G is a full homomorphism of G to H. A minimal H-obstruction is a graph G which does not admit a full H-colouring, such that each proper induced subgraph of G admits a full H-colouring. We analyse minimal H-obstructions using our results on point determining graphs. We connect the two problems by proving that if H has k vertices, then a graph with k+1 vertices is a minimal H-obstruction if and only if it is a realization of H. We conclude that every minimal H-obstruction has at most k+1 vertices, and there are at most two minimal H-obstructions with k+1 vertices.We also consider full homomorphisms to graphs H in which loops are allowed. If H has ? loops and k vertices without loops, then every minimal H-obstruction has at most (k+1)(?+1) vertices, and, when both k and ? are positive, there is at most one minimal H-obstruction with (k+1)(?+1) vertices.In particular, this yields a finite forbidden subgraph characterization of full H-colourability, for any graph H with loops allowed.     

Amply regular graphs and block designs

We study the amply regular diameter d graphs Γ such that for some vertex a the set of vertices at distance d from a is the set of points of a 2-design whose set of blocks consists of the intersections of the neighborhoods of points with the set of vertices at distance d-1 from a. We prove that the subgraph induced by the set of points is a clique, a coclique, or a strongly regular diameter 2 graph. For diameter 3 graphs we establish that this construction is a 2-design for each vertex a if and only if the graph is distance-regular and for each vertex a the subgraph Γ₃(a) is a clique, a coclique, or a strongly regular graph. We obtain the list of admissible parameters for designs and diameter 3 graphs under the assumption that the subgraph induced by the set of points is a Seidel graph. We show that some of the parameters found cannot correspond to distance-regular graphs.     

A characterization of complete matroid base graphs

This study grew from an attempt to give a local analysis of matroid base graphs. A neighborhood-preserving covering of graphs p:G → H is one such that p restricted to every neighborhood in G is an isomorphism. This concept arises naturally when considering graphs with a prescribed set of local properties. A characterization is given of all connected graphs with two local properties: (a) there is a pair of adjacent points, the intersection of whose neighborhoods does not contain three mutually nonadjacent points; (b) the intersection of the neigh-borhoods of points two apart is a 4-cycle. Such graphs have neighborhoods of the form K_n × K_m for fixed n, m and are either complete matroid base graphs or are their images under neighborhood-preserving coverings. If n ≠ m, the graph is unique; if n = m, there are n ? 3 such images which are nontrivial. These examples prove that no set of properties of bounded diameter can characterize matroid base graphs.     

Terwilliger graphs with μ ≤ 3

A Terwilliger graph is a noncomplete graph in which the intersection of the neighborhoods of any two vertices at distance 2 from each other is a μ-clique. We classify connected Terwilliger graphs with μ = 3 and describe the structure of Terwilliger graphs of diameter 2 with μ = 2.     

Empty region graphs

A family of proximity graphs, called Empty Region Graphs (ERG) is presented. The vertices of an ERG are points in the plane, and two points are connected if their neighborhood, defined by a region, does not contain any other point. The region defining the neighborhood of two points is a parameter of the graph. This way of defining graphs is not new, and ERGs include several known proximity graphs such as Nearest Neighbor Graphs, β-Skeletons or Θ-Graphs. The main contribution is to provide insight and connections between the definition of ERG and the properties of the corresponding graphs.We give conditions on the region defining an ERG to ensure a number of properties that might be desirable in applications, such as planarity, connectivity, triangle-freeness, cycle-freeness, bipartiteness and bounded degree. These conditions take the form of what we call tight regions: maximal or minimal regions that a region must contain or be contained in to make the graph satisfy a given property. We show that every monotone property has at least one corresponding tight region; we discuss possibilities and limitations of this general model for constructing a graph from a point set.     

The edge nucleus of a point-determining graph

In this paper we investigate the edge nucleus E⁰(G) of a point-determining graph G. We observe several relationships between E⁰(G) and the nucleus G⁰ = {v ∈ V(G)∣ G ? v is point determining} and use these relationships to prove several properties of E⁰(G). In particular, we show that there are only a finite number of graphs with a given edge nucleus and we determine those graphs G for which |E⁰(G)| ≤ 2. We also show that an n-clique of a point-determining graph G contains at least n?2 edges of E⁰(G) and if G is totally point determining, then every odd cycle of G meets E⁰(G).     

On <Emphasis Type="Italic">K</Emphasis><Subscript>1,3</Subscript>-free strictly Deza graphs

A graph on v vertices is called a Deza graph with parameters (v, k, b, a) if it is k-regular and the number of common neighbors of two distinct vertices takes on one of two values. We describe strictly Deza graphs that do not contain K _1,3 among their induced subgraphs and are unions of closed neighborhoods of two nonadjacent vertices. The latter condition means that there are two nonadjacent vertices such that any other vertex is adjacent to at least one of the them.     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

On the Van Vleck theorem for limit-periodic continued fractions of general form

J. Koolen posed the problem of studying distance-regular graphs in which neighborhoods of vertices are strongly regular graphs with nonprincipal eigenvalue at most t for a given positive integer t. This problem was solved earlier for t = 3. In the case t = 4, the problem was reduced to studying graphs in which neighborhoods of vertices have parameters (352,26,0,2), (352,36,0,4), (243,22,1,2), (729,112,1,20), (204,28,2,4), (232,33,2,5), (676,108,2,20), (85,14,3,2), or (325,54,3,10). In the present paper, we prove that a distance-regular graph in which neighborhoods of vertices are strongly regular with parameters (85, 14, 3, 2) or (325, 54, 3, 10) has intersection array {85, 70, 1; 1, 14, 85} or {325, 270, 1; 1, 54, 325}. In addition, we find possible automorphisms of a graph with intersection array {85, 70, 1; 1, 14, 85}.     

Relaxed Locally Identifying Coloring of Graphs

A locally identifying coloring (lid-coloring) of a graph is a proper vertex-coloring such that the sets of colors appearing in the closed neighborhoods of any pair of adjacent vertices having distinct neighborhoods are distinct. Our goal is to study a relaxed locally identifying coloring (rlid-coloring) of a graph that is similar to locally identifying coloring for which the coloring is not necessarily proper. We denote by \(\chi _{rlid}(G)\) the minimum number of colors used in a relaxed locally identifying coloring of a graph G. In this paper, we prove that the problem of deciding that \(\chi _{rlid}(G)=3\) for a 2-degenerate planar graph G is NP-complete and for a bipartite graph G is polynomial. We give several bounds of \(\chi _{rlid}(G)\) for different families of graphs and construct new graphs for which these bounds are tight. We also compare this parameter with the minimum number of colors used in a locally identifying coloring of a graph G (\(\chi _{lid}(G)\)), the size of a minimum identifying code of G (\(\gamma _{id}(G)\)) and the chromatic number of G (\(\chi (G)\)).     

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.     

Some perfect coloring properties of graphs

A Grundy n-coloring of a finite graph is a coloring of the points of the graph with the non-negative integers smaller than n such that each point is adjacent to some point of each smaller color but to none of the same color. The Grundy number of a graph is the maximum n for which it has a Grundy n-coloring. Characterizations are given of the families of finite graphs G such that for each induced subgraph H of G: (1) the Grundy number of H is equal to the chromatic number of H; (2) the Grundy number of H is equal to the maximum clique size of H; (3) the achromatic number of H is equal to the chromatic number of H; (4) the achromatic number of H is equal to the maximum clique size of H. The definitions are further extended to infinite graphs, and some of the above characterizations are shown to be true for denumerable graphs and locally finite 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.     

Set graphs. I. Hereditarily finite sets and extensional acyclic orientations

A graph $G$ is said to be a set graph if it admits an acyclic orientation which is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set.In this paper, we initiate the study of set graphs. On the one hand, we identify several necessary conditions that every set graph must satisfy. On the other hand, we show that set graphs form a rich class of graphs containing all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation. Inspired by manipulations of hereditarily finite sets, we give simple proofs of two well-known results about claw-free graphs. We give a complete characterization of unicyclic set graphs, and point out two NP-complete problems closely related to the problem of recognizing set graphs. Finally, we argue that these three problems are solvable in linear time on graphs of bounded treewidth.     

Unique eccentric point graphs

A graph G is defined to be a unique eccentric point graph (a u.e.p. graph) if each point of G has a unique maximum distance point. Here u.e.p. graphs which are self-centered are characterized. Two construction procedures are given for generating families of u.e.p. graphs from known u.e.p. graphs. Furthermore, some special classes of u.e.p. graphs are studied in detail.