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.     

Semi-hyper-connected edge transitive graphs

A graph G is said to be hyper-connected if the removal of every minimum cut creates exactly two connected components, one of which is an isolated vertex. In this paper, we first generalize the concept of hyper-connected graphs to that of semi-hyper-connected graphs: a graph G is called semi-hyper-connected if the removal of every minimum cut of G creates exactly two components. Then we characterize semi-hyper-connected edge transitive graphs.     

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.     

Nuclei for totally point determining graphs

The nucleus (edge nucleus) of a point determining graph is defined by Geoffroy and Sumner to be the set of all points (edges) whose removal leaves the graph point determining. It is the purpose of this paper to develop the analogous concepts for totally point determining graphs, that is, graphs in which distinct points have distinct neighborhoods and closed neighborhoods.     

On integral sum graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous related results are also presented.     

On Integral Sum Graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous relative results are also presented.     

Pointwise recurrent homeomorphisms with stable fixed points

We prove that a pointwise recurrent, orientation preserving homeomorphism of the 2-sphere, which is different from the identity and whose fixed points are stable in the sense of Lyapunov must have exactly two fixed points. If moreover there are no periodic points, other than fixed, then every stable minimal set is connected and its complement has exactly two connected components. Finally, we study liftings of the restriction to the complement of the fixed point set to the universal covering space.     

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.     

Tank-Ring Factors in Supereulerian Claw-Free Graphs

A graph G has a tank-ring factor F if F is a connected spanning subgraph with all vertices of degree 2 or 4 that consists of one cycle C and disjoint triangles attaching to exactly one vertex of C such that every component of G ? C contains exactly two vertices. In this paper, we show the following results. (1) Every supereulerian claw-free graph G with 1-hourglass property contains a tank-ring factor. (2) Every supereulerian claw-free graph with 2-hourglass property is Hamiltonian.     

Optimally super-edge-connected transitive graphs

Let X=(V,E) be a connected regular graph. X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ′(X) of X is the minimum number of edges whose removal disconnects X into non-trivial components. A super-edge-connected k-regular graph is said to be optimally super-edge-connected if its restricted edge connectivity attains the maximum 2k−2. In this paper, we define the λ′-atoms of graphs with respect to restricted edge connectivity and show that if X is a k-regular k-edge-connected graph whose λ′-atoms have size at least 3, then any two distinct λ′-atoms are disjoint. Using this property, we characterize the super-edge-connected or optimally super-edge-connected transitive graphs and Cayley graphs. In particular, we classify the optimally super-edge-connected quasiminimal Cayley graphs and Cayley graphs of diameter 2. As a consequence, we show that almost all Cayley graphs are optimally super-edge-connected.     

Locally petersen graphs

A graph Γ is locally Petersen if, for each point t of Γ, the graph induced by Γ on all points adjacent to t is isomorphic to the Petersen graph. We prove that there are exactly three isomorphism classes of connected, locally Petersen graphs and further characterize these graphs by certain of their parameters.     

On Commuting Graph of Group Ring $Z_nS_3$

The commuting graph of an arbitrary ring $R$, denoted by $Γ(R)$, is a graph whose vertices are all non-central elements of $R$, and two distinct vertices $a$ and $b$ are adjacent if and only if $ab = ba$. In this paper, we investigate the connectivity and the diameter of $Γ(Z_n S_3)$. We show that $Γ(Z_n S_3)$ is connected if and only if $n$ is not a prime number. If $Γ(Z_n S_3)$ is connected then diam $(Γ(Z_n S_3)) = 3$, while if $Γ(Z_n S_3)$ is disconnected then every connected component of $Γ(Z_n S_3)$ must be a complete graph with same size, and we completely determine the vertice set of every connected component.     

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.     

Planar unit-distance graphs having planar unit-distance complement

A graph G=(V,E) is called a unit-distance graph in the plane if there is an embedding of V into the plane such that every pair of adjacent vertices are at unit distance apart. If an embedding of V satisfies the condition that two vertices are adjacent if and only if they are at unit distance apart, then G is called a strict unit-distance graph in the plane. A graph G is a (strict) co-unit-distance graph, if both G and its complement are (strict) unit-distance graphs in the plane. We show by an exhaustive enumeration that there are exactly 69 co-unit-distance graphs (65 are strict co-unit-distance graphs), 55 of which are connected (51 are connected strict co-unit-distance graphs), and seven are self-complementary.     

Graphs with 1-Hamiltonian-connected cubes

The cube G³ of a connected graph G is that graph having the same vertex set as G and in which two distinct vertices are adjacent if and only if their distance in G is at most three. A Hamiltonian-connected graph has the property that every two distinct vertices are joined by a Hamiltonian path. A graph G is 1-Hamiltonian-connected if, for every vertex w of G, the graphs G and G?w are Hamiltonian-connected. A characterization of graphs whose cubes are 1-Hamiltonian-connected is presented.     

Semi-hyper-connected vertex transitive graphs

A graph G is said to be semi-hyper-connected if the removal of every minimum cut of G creates exactly two connected components. In this paper, we characterize semi-hyper-connected vertex transitive graphs, in particular Cayley graphs.     

Cut points in some connected topological spaces

We prove that a connected topological space with endpoints has exactly two non-cut points and every cut point is a strong cut point; it follows that such a space is a COTS and the only two non-cut points turn out to be endpoints (in each of the two orders) of the COTS. A non-indiscrete connected topological space with exactly two non-cut points and having only finitely many closed points is proved homeomorphic to a finite subspace of the Khalimsky line. Further, it is shown, without assuming any separation axiom, that in a connected and locally connected topological space X, for a, b in X, S[a,b] is compact whenever it is closed. Using this result we show that an H(i) connected and locally connected topological space with exactly two non-cut points is a compact COTS with end points.     

Unavoidable Configurations in Complete Topological Graphs

A topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by Jordan curves connecting the corresponding points, with the property that any two curves have at most one point in common. We define two canonical classes of topological complete graphs, and prove that every topological complete graph with n vertices has a canonical subgraph of size at least clog^1/8 n, which belongs to one of these classes. We also show that every complete topological graph with n vertices has a non-crossing subgraph isomorphic to any fixed tree with at most clog^1/6 n vertices.     

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.     

n-bathycenters

Does there exist a polygon with the property that for a suitable point p in the plane every ray with endpoint p intersects the polygon in exactly n connected components? Does there exist a polygon with the property that there are two such points, or three, or a segment of such points? For polygon P call a point p with the property that every ray from p intersects P in exactly n connected components n-isobathic with respect to P. Define the n-bathycenter of a polygon P as the set of all points p that are n-isobathic with respect to P. Further define a set S to be an n-bathycenter if there exists a polygon P of which S is the n-bathycenter. This paper deals with the characterization of 2- and 3-bathycenters, together with some results on the general case.