Embeddings of chemical graphs in hypercubes

We study planar graphs embedded in the plane that have chemical applications: the degrees of all vertices are 3 or 2, all internal faces but one or two arer-gons, and each internal face is a simply connected domain. For wide classes of such graphs, we solve the existence problem for embeddings of the graph metric on the vertices in multidimensional cubes or cubical lattices preserving or doubling all the distances. Incidentally we present a complete classification of some interesting families of such graphs. Translated fromMatematicheskie Zametki, Vol. 68, No. 3, pp. 339–352, September, 2000.     

Coedge regular graphs without 3-stars

We describe coedge regular graphs such that antineighborhoods of their vertices are coedge regular graphs with the same value of the parameterμ. As a consequence of the main theorem, we obtain a classification of coedge regular graphs without 3-stars. Translated fromMatematicheskie Zametki, Vol. 60, No. 4, pp. 495–503, October, 1996. This research was supported by the Russion Foundation for Basic Research under grants No. 93-01-01529 and No. 94-01-00802a.     

Recognizing Planar Strict Quasi-Parity Graphs

 A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with no odd chordless path between them (an “even pair”). We present an O(n ³) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9]. Received: September 21, 1998 Final version received: May 9, 2000     

Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs

The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of 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].     

Vertex Cuts

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved by analyzing the action of the group on a structure tree and Tutte used a structure tree to investigate finite 2‐connected graphs, that are not 3‐connected. Most of these structure tree theories have been based on edge cuts, which are components of the graph obtained by removing finitely many edges. A new axiomatic theory is described here using vertex cuts, components of the graph obtained by removing finitely many vertices. This generalizes Tutte's decomposition of 2‐connected graphs to k‐connected graphs for any k, in finite and infinite graphs. The theory can be applied to nonlocally finite graphs with more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a decomposition for a group acting on such a graph, generalizing Stallings' theorem. Further applications include the classification of distance transitive graphs and k‐CS‐transitive graphs.     

Half-Transitive Graphs of Prime-Cube Order

We call an undirected graph X half-transitive if the automorphism group Aut X of X acts transitively on the vertex set and edge set but not on the set of ordered pairs of adjacent vertices of X. In this paper we determine all half-transitive graphs of order p ³ and degree 4, where p is an odd prime; namely, we prove that all such graphs are Cayley graphs on the non-Abelian group of order p ³ and exponent p ², and up to isomorphism there are exactly (p – 1)/2 such graphs. As a byproduct, this proves the uniqueness of Holt's half-transitive graph with 27 vertices.     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010     

Matching signatures and Pfaffian graphs

Perfect matchings of k-Pfaffian graphs may be enumerated in polynomial time on the number of vertices, for fixed k. In general, this enumeration problem is #P-complete. We give a Composition Theorem of 2r-Pfaffian graphs from r Pfaffian spanning subgraphs. Constructions of k-Pfaffian graphs known prior to this seem to be of a very different and essentially topological nature. We apply our Composition Theorem to produce a bipartite graph on 10 vertices that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine (2009) [8], which states that the Pfaffian number of a graph is a power of four.     

具有较小直径的三类图的对极色数

对一个连通图G,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Four‐terminal reducibility and projective‐planar wye‐delta‐wye‐reducible graphs

A graph is YΔY‐reducible if it can be reduced to a vertex by a sequence of series‐parallel reductions and YΔY‐transformations. Terminals are distinguished vertices, that cannot be deleted by reductions and transformations. In this article, we show that four‐terminal planar graphs are YΔY‐reducible when at least three of the vertices lie on the same face. Using this result, we characterize YΔY‐reducible projective‐planar graphs. We also consider terminals in projective‐planar graphs, and establish that graphs of crossing‐number one are YΔY‐reducible. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 83–93, 2000     

双圈图的Laplace矩阵的谱半径

利用奇异点对的分类,得到了n阶双圈图的Laplace矩阵的谱半径的第二至第八大值,并且刻划了达到这些上界的极图.     

On graphs without crowns with regularμ-subgraphs

Anm-crown is the complete tripartite graphK _{1, 1,m} with parts of order 1, 1,m, and anm-claw is the complete bipartite graphK _1,m with parts of order 1,m, wherem ≥ 3. A vertexa of a graph Γ is calledweakly reduced iff the subgraph {x є Γ ‖a ^⊥ =x ^⊥} consists of one vertex. A graph Γ is calledweakly reduced iff all its vertices are weakly reduced. In the present paper we classify all connected weakly reduced graphs without 3-crowns, all of whose μ-subgraphs are regular graphs of constant nonzero valency. In particular, we generalize the characterization of Grassman and Johnson graphs due to Numata, and the characterization of connected reduced graphs without 3-claws due to Makhnev. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 874–881, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00462.     

A characterization of P4‐indifference graphs

A graph is a P₄‐indifference graph if it admits a linear ordering ≺ on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has either a ≺ b ≺ c ≺ d or d ≺ c ≺ b ≺ a. P₄‐indifference graphs generalize indifference graphs and are perfectly orderable. We give a characterization of P₄‐indifference graphs by forbidden induced subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 155‐162, 1999     

Codes from the incidence matrices of graphs on 3-sets

We examine the p-ary linear codes from incidence matrices of the three uniform subset graphs with vertex set the set of subsets of size 3 of a set of size n, with adjacency defined by two vertices as 3-sets being adjacent if they have zero, one or two elements in common, respectively. All the main parameters of the codes and the nature of the minimum words are obtained, and it is shown that the codes can be used for full error-correction by permutation decoding. We examine also the binary codes of the line graphs of these graphs.     

Bootstrap percolation with inhibition

We study a variant of the classical bootstrap percolation process on Erd?s Rényi random graphs. The graphs we consider have inhibitory vertices obstructing the diffusion of activity and excitatory vertices facilitating it. We study both a synchronous and an asynchronous version of the process. Both begin with a small initial set of active vertices, and the activation spreads to all vertices for which the number of excitatory active neighbors exceeds the number of inhibitory active neighbors by a certain amount. We show that in the synchronous process, inhibitory vertices may cause unstable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. We further show that in the asynchronous model the process becomes stable and stops with an active set containing a nontrivial deterministic constant fraction of all vertices. Moreover, we show that percolation occurs significantly faster asynchronously than synchronously.     

Characterizing planarity using theta graphs

A theta graph is a homeomorph of K_2,3. In an embedded planar graph the local rotation at one degree-three vertex of a theta graph determines the local rotation at the other degree-three vertex. Using this observation, we give a characterization of planar graphs in terms of balance in an associated signed graph whose vertices are K_1,3 subgraphs and whose edges correspond to theta graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 17–20, 1998     

Binary Codes of Strongly Regular Graphs

For strongly regular graphs ith adjacency matrix A, we look at the binary codes generated by A and A + I. We determine these codes for some families of graphs, e pay attention to the relation beteen the codes of switching equivalent graphs and, ith the exception of two parameter sets, we generate by computer the codes of all knon strongly regular graphs on fewer than 45 vertices.     

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.”