DNA recombination through assembly graphs

Motivated by DNA rearrangements and DNA homologous recombination modeled in [A. Angeleska, N. Jonoska, M. Saito, L.F. Landweber, RNA-guided DNA assembly, Journal of Theoretical Biology, 248(4) (2007), 706–720], we investigate smoothings on graphs that consist of only 4-valent and 1-valent rigid vertices, called assembly graphs. An assembly graph can be seen as a representation of the DNA during certain recombination processes in which 4-valent vertices correspond to the alignment of the recombination sites. A single gene is modeled by a polygonal path in an assembly graph. A polygonal path makes a “right-angle” turn at every vertex, defining smoothings at the 4-valent vertices and therefore modeling the recombination process. We investigate the minimal number of polygonal paths visiting all vertices of a given graph exactly once, and show that for every positive integer n there are graphs that require at least n such polygonal paths. We show that there is an embedding in three-dimensional space of each assembly graph such that smoothing of vertices according to a given set of polygonal paths results in an unlinked graph. As some recombination processes may happen simultaneously, we characterize the subsets of vertices whose simultaneous smoothings keep a given gene in tact and give a characterization of all sequences of sets of vertices defining successive simultaneous smoothings that can realize complete gene rearrangement.     

Cubical d-Polytopes with Few Vertices for d>4

A cubical polytope is a convex polytope all of whose facets are combinatorial cubes. A d-polytope P is called almost simple if, in the graph of P, each vertex of P is d-valent or (d+1)-valent. We show that, for d>4, all but one cubicald -polytopes with up to 2 ^d+1 vertices are almost simple. This provides a complete enumeration of all the cubical d-polytopes with up to 2 ^d+1 vertices, for d>4.     

Cubical 4-Polytopes with Few Vertices

A cubical polytope is a convex polytope all of whose facets are conbinatorial cubes. A d-polytope Pis called almost simple if, in the graph of P, each vertex of Pis d-valent of (d+ 1)-valent. It is known that, for d> 4, all but one cubical d-polytopes with up to 2^d+1vertices are almost simple, which provides a complete enumeration of all the cubical d-polytopes with up to 2^d+1vertices. We show that this result is also true for d=4.     

On Narrow Hexagonal Graphs with a 3-Homogeneous Suborbit

A connected graph of girth m 3 is called a polygonal graph if it contains a set of m-gons such that every path of length two is contained in a unique element of the set. In this paper we investigate polygonal graphs of girth 6 or more having automorphism groups which are transitive on the vertices and such that the vertex stabilizers are 3-homogeneous on adjacent vertices. We previously showed that the study of such graphs divides naturally into a number of substantial subcases. Here we analyze one of these cases and characterize the k-valent polygonal graphs of girth 6 which have automorphism groups transitive on vertices, which preserve the set of special hexagons, and which have a suborbit of size k – 1 at distance three from a given vertex.     

Further results on monotonic graph invariants and bipartiteness number

Abstract

The bipartiteness of a graph is the minimum number of vertices whose deletion from G results in a bipartite graph. If a graph invariant decreases or increases with addition of edges of its complement, then it is called a monotonic graph invariant. In this article, we determine the extremal values of some famous monotonic graph invariants, and characterize the corresponding extremal graphs in the class of all connected graphs with a given vertex bipartiteness.     

A refinement of the Conway-Gordon theorems

In 1983, Conway-Gordon showed that for every spatial complete graph on 6 vertices, the sum of the linking numbers over all of the constituent 2-component links is congruent to 1 modulo 2, and for every spatial complete graph on 7 vertices, the sum of the Arf invariants over all of the Hamiltonian knots is also congruent to 1 modulo 2. In this article, we give integral lifts of the Conway-Gordon theorems above in terms of the square of the linking number and the second coefficient of the Conway polynomial. As applications, we give alternative topological proofs of theorems of Brown-Ramírez Alfonsín and Huh-Jeon for rectilinear spatial complete graphs which were proved by computational and combinatorial methods.     

A construction of 3-connected graphs

We show that the 3-connected graphs can be generated from the complete graph on four vertices and the complete 3,3 bipartite graph by adding vertices and adding edges with endpoints on two edges meeting at a 3-valent vertex.     

The regular polyhedra of type {p, 3} with 2p vertices

G(p, d) is a cubic (3-valent) graph consisting of a p-gon and a (p/d)-gon (a starpolygon) with corresponding vertices joined (the notation admits anomalous cases, when d=1 or (d, p)>1), and with a high degree of symmetry. It is shown here that the seven possible graphs G(p, d) are just the edge-graphs of the regular polyhedra of type {p, 3} with 2p vertices, and therefore 3p edges, 6 faces, and symmetry group of order 12p.     

Globally Linked Pairs of Vertices in Equivalent Realizations of Graphs

A two-dimensional framework (G,p) is a graph G = (V,E) together with a map p: V → ℝ². We view (G,p) as a straight line realization of G in ℝ². Two realizations of G are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices {u,v} is globally linked in G if %and for all equivalent frameworks (G,q), the distance between the points corresponding to u and v is the same in all pairs of equivalent generic realizations of G. The graph G is globally rigid if all of its pairs of vertices are globally linked. We extend the characterization of globally rigid graphs given by the first two authors [13] by characterizing globally linked pairs in M-connected graphs, an important family of rigid graphs. As a byproduct we simplify the proof of a result of Connelly [6] which is a key step in the characterization of globally rigid graphs. We also determine the number of distinct realizations of an M-connected graph, each of which is equivalent to a given generic realization. Bounds on this number for minimally rigid graphs were obtained by Borcea and Streinu in [3].     

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.     

Longest cycles in polyhedral graphs

A sequence of polyhedral graphsG _n is constructed, having only 3-valent and 8-valent vertices and having only 3-gons and 8-gons as faces with the property that the shortness exponent of the sequence as well as the shortness exponent of the sequence of duals is smaller than one.     

Convexities related to path properties on graphs

A feasible family of paths in a connected graph G is a family that contains at least one path between any pair of vertices in G. Any feasible path family defines a convexity on G. Well-known instances are: the geodesics, the induced paths, and all paths. We propose a more general approach for such ‘path properties’. We survey a number of results from this perspective, and present a number of new results. We focus on the behaviour of such convexities on the Cartesian product of graphs and on the classical convexity invariants, such as the Carathéodory, Helly and Radon numbers in relation with graph invariants, such as the clique number and other graph properties.     

Star coloring planar graphs from small lists

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324–337, 2010     

Local structure of 5- and 6-connected graphs

We prove that if graph on n vertices is minimally and contraction critically 5-connected, then it has 4n/7 vertices of degree 5. We also prove that if graph on n vertices is minimally and contraction critically 6-connected, then it has n/2 vertices of degree 6. Bibliography: 7 titles.     

Non-Hamiltonian non-Grinbergian graphs

Settling a question of Tutte and a similar question of Grünbaum and Zaks, we present a 3-valent 3-connected planar graph that has only pentagons and octagons, has 92 (200, respectively) vertices and its longest circuit (path, respectively) contains at most 90 (198, respectively) vertices; moreover, it is shown that the family of all 3-valent 3-connected planar graphs, having n-gons only if n≡ 2 (mod3) (or n≡ 1 (mod3)), has a shortness exponent which is less than one.     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

Graphs with constant link and small degree or order

The graph G has constant link L if for each vertex x of G the graph induced by G on the vertices adjacent to x is isomorphic to L. For each graph L on 6 or fewer vertices we decide whether or not there exists a graph G with constant link L. From this we are able to list all graphs on 11 or fewer vertices which have constant link.     

I-hedrite图平面嵌入的唯一性

本文研究每一个面圈的圈长仅为2,3或4的无割点的4·正则连通平面图,称之为I-hedrite图.证明在相等意义上,I-hedrite图的平面嵌入是唯一的.这个唯一性结论意味着,两个i-hedrite图(即每一个面的度仅为2,3或4的4-正则连通平图)是相等的当且仅当它们是同构的,从而解决了i-hedrite图的同构构造在相等意义上的唯一性问题.     

A lower bound for groupies in graphs

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contain at least one groupie, the graph K_n − e contains just 2 groupie vertices for n ≥ 2. In this paper we derive a lower bound for the number of groupies which shows, in particular, that any graph with 2 or more vertices must contain at least 2 groupies. © 1996 John Wiley & Sons, Inc.     

Flag algebras and the stable coefficients of the Jones polynomial

We study the structure of the stable coefficients of the Jones polynomial of an alternating link. We start by identifying the first four stable coefficients with polynomial invariants of a (reduced) Tait graph of the link projection. This leads us to introduce a free polynomial algebra of invariants of graphs whose elements give invariants of alternating links which strictly refine the first four stable coefficients. We conjecture that all stable coefficients are elements of this algebra, and give experimental evidence for the fifth and the sixth stable coefficient. We illustrate our results in tables of all alternating links with at most 10 crossings and all irreducible planar graphs with at most 6 vertices.