Hamiltonicity in vertex envelopes of plane cubic graphs

In this paper we study a graph operation which produces what we call the “vertex envelope” G^∗_V from a graph G. We apply it to plane cubic graphs and investigate the hamiltonicity of the resulting graphs, which are also cubic. To this end, we prove a result giving a necessary and sufficient condition for the existence of hamiltonian cycles in the vertex envelopes of plane cubic graphs. We then use these conditions to identify graphs or classes of graphs whose vertex envelopes are either all hamiltonian or all non-hamiltonian, paying special attention to bipartite graphs. We also show that deciding if a vertex envelope is hamiltonian is NP-complete, and we provide a polynomial algorithm for deciding if a given cubic plane graph is a vertex envelope.     

Fastest mixing Markov chain problem for the union of two cliques

A symmetric, random walk on a graph G can be defined by prescribing weights to the edges in such a way that for each vertex the sum of the weights of the edges incident to the vertex is at most one. The fastest mixing, Markov chain (FMMC) problem for G is to determine the weighting that yields the fastest mixing random walk. We solve the FMMC problem in the case that G is the union of two complete graphs.     

Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].     

On types of growth for graph-different permutations

We consider an infinite graph G whose vertex set is the set of natural numbers and adjacency depends solely on the difference between vertices. We study the largest cardinality of a set of permutations of [n] any pair of which differ somewhere in a pair of adjacent vertices of G and determine it completely in an interesting special case. We give estimates for other cases and compare the results in case of complementary graphs. We also explore the close relationship between our problem and the concept of Shannon capacity “within a given type.”     

The homotopical reduction of a nearest neighbor random walk*

Consider a nearest neighbor random walk on a graph G and discard all the segments of its trajectory that are homotopically equivalent to a single point. We prove that if the lift of the random walk to the covering tree of G is transient, then the resulting reduced trajectories induce a Markov chain on the set of oriented edges of G. We study this chain in relation with the original random walk. As an intermediate result, we give a simple proof of the Markovian structure of the harmonic measure on trees.* Supported by Nucleus Millennium Information and Randomness ICM P01-005.     

Growth Series and Random Walks on Some Hyperbolic Graphs

 Consider the tessellation of the hyperbolic plane by m-gons, ℓ per vertex. In its 1-skeleton, we compute the growth series of vertices, geodesics, tuples of geodesics with common extremities. We also introduce and enumerate holly trees, a family of proper loops in these graphs. We then apply Grigorchuk’s result relating cogrowth and random walks to obtain lower estimates on the spectral radius of the Markov operator associated with a symmetric random walk on these graphs.     

Multiple cover time

Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within a constant factor of the number of times predicted by the stationary distribution. Thus the blanket time is, essentially, the number of steps required of a random walk in order that the observed distribution reflect the stationary distribution. We provide substantial evidence for the following conjecture: that the blanket time of a graph never exceeds the cover time by more than a constant factor. In other words, at the cost of a multiplicative constant one can hit every vertex often instead of merely once. We prove the conjecture in the case where the cover time and maximum hitting time differ by a logarithmic factor. This case includes almost all graphs, as well as most “natural” graphs: the hypercube, k-dimensional lattices for k ≥ 2, balanced k-ary trees, and expanders. We further prove the conjecture for perhaps the most natural graphs not falling in the above case: paths and cycles. Finally, we prove the conjecture in the case of independent stochastic processes. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 403–411 (1996)     

Growth Series and Random Walks on Some Hyperbolic Graphs

 Consider the tessellation of the hyperbolic plane by m-gons, ℓ per vertex. In its 1-skeleton, we compute the growth series of vertices, geodesics, tuples of geodesics with common extremities. We also introduce and enumerate holly trees, a family of proper loops in these graphs. We then apply Grigorchuk’s result relating cogrowth and random walks to obtain lower estimates on the spectral radius of the Markov operator associated with a symmetric random walk on these graphs. Received 19 September 2001; in revised form 23 December 2001     

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.     

On the extremal Merrifield-Simmons index and Hosoya index of quasi-tree graphs

It is well known that the two graph invariants, “the Merrifield-Simmons index” and “the Hosoya index” are important in structural chemistry. A graph G is called a quasi-tree graph, if there exists u₀ in V(G) such that G−u₀ is a tree. In this paper, at first we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest Merrifield-Simmons indices. Then we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest Hosoya indices, as well as those n-vertex quasi-tree graphs with k pendent vertices having the smallest Hosoya index.     

Random Graph Coverings I: General Theory and Graph Connectivity

In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n, we form a random graph by replacing each vertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G. The resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also "randomizing" given graphs. The main specific result that we prove here (Theorem 1) is that if is the smallest vertex degree in G, then almost all n-covers of G are -connected. In subsequent papers we will address other graph properties, such as girth, expansion and chromatic number. Received June 21, 1999/Revised November 16, 2000 RID="*" ID="*" Work supported in part by grants from the Israel Academy of Aciences and the Binational Israel-US Science Foundation.     

Spanning forests and the golden ratio

For a graph G, let f_ij be the number of spanning rooted forests in which vertex j belongs to a tree rooted at i. In this paper, we show that for a path, the f_ij's can be expressed as the products of Fibonacci numbers; for a cycle, they are products of Fibonacci and Lucas numbers. The doubly stochastic graph matrix is the matrix F=(f_ij)_n×n/f, where f is the total number of spanning rooted forests of G and n is the number of vertices in G. F provides a proximity measure for graph vertices. By the matrix forest theorem, F^-1=I+L, where L is the Laplacian matrix of G. We show that for the paths and the so-called T-caterpillars, some diagonal entries of F (which provide a measure of the self-connectivity of vertices) converge to φ^-1 or to 1-φ^-1, where φ is the golden ratio, as the number of vertices goes to infinity. Thereby, in the asymptotic, the corresponding vertices can be metaphorically considered as “golden introverts” and “golden extroverts,” respectively. This metaphor is reinforced by a Markov chain interpretation of the doubly stochastic graph matrix, according to which F equals the overall transition matrix of a random walk with a random number of steps on G.     

On resistance of graphs

An edge-coloring of a graph G with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs.     

The spum and sum-diameter of graphs: Labelings of sum graphs

A sum graph is a finite simple graph whose vertex set is labeled with distinct positive integers such that two vertices are adjacent if and only if the sum of their labels is itself another label. The spum of a graph G is the minimum difference between the largest and smallest labels in a sum graph consisting of G and the minimum number of additional isolated vertices necessary so that a sum graph labeling exists. We investigate the spum of various families of graphs, namely cycles, paths, and matchings. We introduce the sum-diameter, a modification of the definition of spum that omits the requirement that the number of additional isolated vertices in the sum graph is minimal, which we believe is a more natural quantity to study. We then provide asymptotically tight general bounds on both sides for the sum-diameter, and study its behavior under numerous binary graph operations as well as vertex and edge operations. Finally, we generalize the sum-diameter to hypergraphs.     

The least eigenvalue of graphs with given connectivity

Let G be a simple graph and A(G) be the adjacency matrix of G. The eigenvalues of G are those of A(G). In this paper, we characterize the graphs with the minimal least eigenvalue among all graphs of fixed order with given vertex connectivity or edge connectivity.     

The energy of random graphs

In 1970s, Gutman introduced the concept of the energy E(G) for a simple graph G, which is defined as the sum of the absolute values of the eigenvalues of G. This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner’s semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs.     

Clique-width of graphs defined by one-vertex extensions

Let G be a graph and u be a vertex of G. We consider the following operation: add a new vertex v such that v does not distinguish any two vertices which are not distinguished by u. We call this operation a one-vertex extension. Adding a true twin, a false twin or a pendant vertex are cases of one-vertex extensions. Here we are interested in graph classes defined by a subset of allowed one-vertex extension. Examples are trees, cographs and distance-hereditary graphs. We give a complete classification of theses classes with respect to their clique-width. We also introduce a new graph parameter called the modular-width, and we give a relation with the clique-width.     

A note on the last new vertex visited by a random walk

A “cover tour” of a connected graph G from a vertex x is a random walk that begins at x, moves at each step with equal probability to any neighbor of its current vertex, and ends when it has hit every vertex of G. The cycle C_n is well known to have the curious property that a cover tour from any vertex is equally likely to end at any other vertex; the complete graph K_n shares this property, trivially, by symmetry. Ronald L. Graham has asked whether there are any other graphs with this property; we show that there are not. © 1993 John Wiley & Sons, Inc.     

Random mappings of scaled graphs

Given a connected finite graph Γ with a fixed base point O and some graph G with a based point we study random 1-Lipschitz maps of a scaled Γ into G. We are mostly interested in the case where G is a Cayley graph of some finitely generated group, where the construction does not depend on the choice of base points. A particular case of Γ being a graph on two vertices and one edge corresponds to the random walk on G, and the case where Γ is a graph on two vertices and two edges joining them corresponds to Brownian bridge in G. We show, that unlike in the case ${G=\mathbb Z^d}$ , the asymptotic behavior of a random scaled mapping of Γ into G may differ significantly from the asymptotic behavior of random walks or random loops in G. In particular, we show that this occurs when G is a free non-Abelian group. Also we consider the case when G is a wreath product of ${\mathbb Z}$ with a finite group. To treat this case we prove new estimates for transition probabilities in such wreath products. For any group G generated by a finite set S we define a functor E from category of finite connected graphs to the category of equivalence relations on such graphs. Given a finite connected graph Γ, the value E _G,S (Γ) can be viewed as an asymptotic invariant of G.