Realizability of Graphs in Three Dimensions

This paper concludes the characterization of 3-realizable graphs begun by Belk and Connelly. A graph is 3-realizable if, for every configuration of its vertices in E^N with N ≥ 3, there exists a corresponding configuration in E³ with the same edge lengths. In this paper the two graphs V₈ and C₅ × C₂ are shown to be 3-realizable. As shown by Belk and Connelly, this means that the forbidden minors for 3-realizability are K₅ and K_2,2,2.A graph is d-realizable if, for every configuration of its vertices in E^N, there exists a another corresponding configuration in E^d with the same edge lengths.     

Problems of distance geometry and convex properties of quadratic maps

A weighted graph is calledd-realizable if its vertices can be chosen ind-dimensional Euclidean space so that the Euclidean distance between every pair of adjacent vertices is equal to the prescribed weight. We prove that if a weighted graph withk edges isd-realizable for somed, then it isd-realizable for (this bound is sharp in the worst case). We prove that for a graphG withn vertices andk edges and for a dimensiond the image of the so-called rigidity map ℝ ^dn →ℝ ^k is a convex set in ℝ ^k provided . These results are obtained as corollaries of a general convexity theorem for quadratic maps which also extends the Toeplitz-Hausdorff theorem. The main ingredients of the proof are the duality for linear programming in the space of quadratic forms and the “corank formula” for the strata of singular quadratic forms. This research was supported by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C0027.     

Two characterizations of chain partitioned probe graphs

Chain graphs are exactly bipartite graphs without induced 2K ₂ (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G ^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m ²)-time recognition algorithm for chain partitioned probe graphs.     

Generic Global Rigidity

Suppose a finite configuration of labeled points p = (p₁,. . . ,p_n) in E^d is given along with certain pairs of those points determined by a graph G such that the coordinates of the points of p are generic, i.e., algebraically independent over the integers. If another corresponding configuration q = (q₁,. . . ,q_n) in E^d is given such that the corresponding edges of G for p and q have the same length, we provide a sufficient condition to ensure that p and q are congruent in E^d. This condition, together with recent results of Jackson and Jordán, give necessary and sufficient conditions for a graph being generically globally rigid in the plane.     

Independent perfect domination sets in Cayley graphs

In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube Q_n has an independent perfect domination set if and only if Q_n is a regular covering of the complete graph K_n+1 if and only if n = 2^m ? 1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213–219, 2001     

Extended F4-buildings and the Baby Monster

Let Τ be the Baby Monster graph which is the graph on the set of {3,4}-transpositions in the Baby Monster group B in which two such transpositions are adjacent if their product is a central involution in B. Then Τ is locally the commuting graph of central (root) involutions in ² E ₆(2). The graph Τ contains a family of cliques of size 120. With respect to the incidence relation defined via inclusion these cliques and the non-empty intersections of two or more of them form a geometry ℰ(B) with diagram for t=4 and the action of B on ℰ(B) is flag-transitive. We show that ℰ(B) contains subgeometries ℰ(² E ₆(2)) and ℰ(Fi ₂₂) with diagrams c.F ₄(2) and c.F ₄(1). The stabilizers in B of these subgeometries induce on them flag-transitive actions of ² E ₆(2):2 and Fi ₂₂:2, respectively. The geometries ℰ(B), ℰ(² E ₆(2)) and ℰ(Fi ₂₂) possess the following properties: (a) any two elements of type 1 are incident to at most one common element of type 2 and (b) three elements of type 1 are pairwise incident to common elements of type 2 if and only if they are incident to a common element of type 5. The paper addresses the classification problem of c.F ₄(t)-geometries satisfying (a) and (b). We construct three further examples for t=2 with flag-transitive automorphism groups isomorphic to 3⋅²E₂:2, E₆(2):2 and 2²⁶ .F₄(2) and one for t=1 with flag-transitive automorphism group 3⋅Fi ₂₂:2. We also study the graph of an arbitrary (non-necessary flag-transitive) c.F ₄(t)-geometry satisfying (a) and (b) and obtain a complete list of possibilities for the isomorphism type of subgraph induced by the common neighbours of a pair of vertices at distance 2. Finally, we prove that ℰ(B) is the only c.F ₄(4)-geometry, satisfying (a) and (b). Oblatum 20-X-1999 & 2-I-2001?Published online: 5 March 2001     

The chain graph sandwich problem

The chain graph sandwich problem asks: Given a vertex set V, a mandatory edge set E ¹, and a larger edge set E ², is there a graph G=(V,E) such that E ¹?E?E ² with G being a chain graph (i.e., a 2K ₂-free bipartite graph)? We prove that the chain graph sandwich problem is NP-complete. This result stands in contrast to (1) the case where E ¹ is a connected graph, which has a linear-time solution, (2) the threshold graph sandwich problem, which has a linear-time solution, and (3) the chain probe graph problem, which has a polynomial-time solution.     

Some results on exclusive sum graphs

Let N(Z) denote the set of all positive integers (integers). The sum graph G ⁺(S) of a finite subset S?N(Z) is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an (integral) sum graph if it is isomorphic to the sum graph of some S?N(Z). A sum labelling S is called an exclusive sum labelling if u+v∈S?V(G) for any edge uv∈E(G). We say that G is labeled exclusively. The least number r of isolated vertices such that G∪rK ₁ is an exclusive sum graph is called the exclusive sum number ε(G) of graph G. In this paper, we discuss the exclusive sum number of disjoint union of two graphs and the exclusive sum number of some graph classes.     

Trivalent 2-Arc Transitive Graphs of Type {G^1_2} are Near Polygonal

A connected graph Σ of girth at least four is called a near n-gonal graph with respect to E, where n ≥  4 is an integer, if E is a set of n-cycles of Σ such that every path of length two is contained in a unique member of E. It is well known that connected trivalent symmetric graphs can be classified into seven types. In this note we prove that every connected trivalent G-symmetric graph S 1 K₄{\Sigma \neq K_4} of type G¹₂{G^1_2} is a near polygonal graph with respect to two G-orbits on cycles of Σ. Moreover, we give an algorithm for constructing the unique cycle in each of these G-orbits containing a given path of length two.     

Note on eccentricities in tournaments

An (n - l)-tuple (b ₁...,b _n-i ) of nonnegative integers isb-realizable if there exists a tournamentT withn vertices such that for each k,1 ≤k ≤inn] ise-realizable if there exists a tournamentT with vertex setV(T) = {v ₁,…v _n } such thate _i is the eccentricity of v_i. In this note we characterizeb-realizable vectors ande-realizable sequences.     

Note on induced subgraphs of the unit distance graphE n

The unit distance graphE ⁿ is the graph whose vertices are the points in Euclideann-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for anyn there is a finite bipartite graph which cannot be embedded inE ⁿ as an induced subgraph and that every finite graph with maximum degreed can be embedded inE ^N ,N=(d ³ –d)/2, as an induced subgraph.     

Regular bipartite graphs are antimagic

A labeling of a graph G is a bijection from E(G) to the set {1, 2,… |E(G)|}. A labeling is antimagic if for any distinct vertices u and v, the sum of the labels on edges incident to u is different from the sum of the labels on edges incident to v. We say a graph is antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every connected graph other than K₂ is antimagic. In this article, we show that every regular bipartite graph (with degree at least 2) is antimagic. Our technique relies heavily on the Marriage Theorem. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 173–182, 2009     

Graphs that admit square 1-factorizations are hamiltonian Cayley graphs

A square 1-factorization of a graph is a 1-factorization in which the union of any two distinct 1-factors is a disjoint union of 4-cycles. We show that a graph admits a square 1-factorization if and only if it is a Cayley graph with group (₂) ⁿ for somen. The rest of the title follows since Cayley graphs of abelian groups are known to be hamiltonian.     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

The spanning subgraphs of eulerian graphs

It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2_m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.     

The Simple Connectedness of a Tame Weakly Shod Algebra

Abstract

We prove that a tame weakly shod algebra A which is not quasi-tilted is simply connected if and only if the orbit graph of its pip-bounded component is a tree, or if and only if its first Hochschild cohomology group H¹(A) with coefficients in _A A _A vanishes. We also show that it is strongly simply connected if and only if the orbit graph of each of its directed components is a tree, or if and only if H¹(A) = 0 and it contains no full convex subcategory which is hereditary of type 𝔸?, or if and only if it is separated and contains no full convex subcategory which is hereditary of type 𝔸?.     

The Zero-Divisor Graphs Which Are Uniquely Determined By Neighborhoods

A nonempty simple connected graph G is called a uniquely determined graph, if distinct vertices of G have distinct neighborhoods. We prove that if R is a commutative ring, then Γ(R) is uniquely determined if and only if either R is a Boolean ring or T(R) is a local ring with x² = 0 for any x ∈ Z(R), where T(R) is the total quotient ring of R. We determine all the corresponding rings with characteristic p for any finite complete graph, and in particular, give all the corresponding rings of K_n if n + 1 = p^q for some primes p, q. Finally, we show that a graph G with more than two vertices has a unique corresponding zero-divisor semigroup if G is a zero-divisor graph of some Boolean ring.     

Sphere and Dot Product Representations of Graphs

A graph G is a k-sphere graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the distance between v _i and v _j is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the dot product of v _i and v _j is at least 1.     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

On an embedding of certainp-groups

It is shown that ap-group with cyclic centre can be embedded in a finite group as a normal subgroup contained in its Frattini subgroup if and only if it is either an extraspecial 2-group of order at least 2⁷ or the central product of a cyclic groupQ of order ≧4 and an extraspecial groupE of order ≧2⁵, amalgamating Ω₁ (Q) and the centre ofE.