Operator decomposition of graphs and the reconstruction conjecture

We present the method of proving the reconstructibility of graph classes based on the new type of decomposition of graphs — the operator decomposition. The properties of this decomposition are described. Using this decomposition we prove the following. Let P and Q be two hereditary graph classes such that P is closed with respect to the operation of join and Q is closed with respect to the operation of disjoint union. Let M be a module of graph G with associated partition (A,B,M), where A∼M and B⁄∼M, such that G[A]∈P, G[B]∈Q and G[M] is not (P,Q)-split. Then the graph G is reconstructible.     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008     

圈的中间图pebbling数和Graham猜想

图G的一个pebbling移动是从一个顶点移走2个pebble, 而把其中的1个pebble移到与其相邻的一个顶点上. 图G 的pebbling数f(G)是最小的正整数n, 使得不论n个pebble 如何放置在G的顶点上, 总可以通过一系列的pebbling移动, 把1个pebble移到图G的任意一个顶点上. 图G 的中间图M(G) 就是在G 的每一条边上插入一个新点, 再把G 上相邻边上的新点用一条边连接起来的图. 对于任意两个连通图G和H, Graham猜测f(G\times H)\leq f(G)f(H). 首先研究了圈的中间图的pebbling 数, 然后讨论了一些圈的中间图满足Graham猜想.     

Embedding arbitrary finite simple graphs into small strongly regular graphs

It is well known that any finite simple graph Γ is an induced subgraph of some exponentially larger strongly regular graph Γ (e.g., [2, 8]). No general polynomial‐size construction has been known. For a given finite simple graph Γ on υ vertices, we present a construction of a strongly regular graph Γ on O(υ⁴) vertices that contains Γ as its induced subgraph. A discussion is included of the size of the smallest possible strongly regular graph with this property. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 1–8, 2000     

An approximate version of Hadwiger's conjecture for claw‐free graphs

Hadwiger's conjecture states that every graph with chromatic number χ has a clique minor of size χ. In this paper we prove a weakened version of this conjecture for the class of claw‐free graphs (graphs that do not have a vertex with three pairwise nonadjacent neighbors). Our main result is that a claw‐free graph with chromatic number χ has a clique minor of size $\lceil\frac{2}{3}\chi\rceil$. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 259–278, 2010     

Vertex reconstruction in Cayley graphs

In this survey paper we review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex x from its r-neighbors, that are, vertices at distance at most r from x, consists of finding the minimum restrictions on the number of r-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group and the hyperoctahedral group (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.     

On the power of a perturbation for testing non-isomorphism of graphs

In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic.This work was supported by the U.S. Army Research Office under Grant DAAG29-82-K-0107.     

Vizing’s conjecture for chordal graphs

Vizing conjectured that γ(G□H)≥γ(G)γ(H) for every pair G,H of graphs, where “□” is the Cartesian product, and γ(G) is the domination number of the graph G. Denote by γⁱ(G) the maximum, over all independent sets I in G, of the minimal number of vertices needed to dominate I. We prove that γ(G□H)≥γⁱ(G)γ(H). Since for chordal graphs γⁱ=γ, this proves Vizing’s conjecture when G is chordal.     

Overfull conjecture for graphs with high minimum degree

Chetwynd and Hilton showed that any regular graph G of even order n which has relatively high degree has a 1‐factorization. This is equivalent to saying that under these conditions G has chromatic index equal to its maximum degree . Using this result, we show that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree has chromatic index equal to its maximum degree providing that G does not contain an “overfull” subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 73–80, 2004     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

Meyniel's conjecture holds for random graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph , which improves upon existing results showing that asymptotically almost surely the cop number of is provided that for some . We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. This will also be used in a separate paper on random d‐regular graphs, where we show that the conjecture holds asymptotically almost surely when . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396–421, 2016     

Partition graphs for finite symmetric groups

This paper outlines an investigation of a class of arc-transitive graphs admitting a finite symmetric group S_n acting primitively on vertices, with vertex-stabilizer isomorphic to the wreath product S_m wr S_r (preserving a partition of {1,2,…n} into r parts of equal size m). Several properties of these graphs are considered, including their correspondence with r × r matrices with constant row- and column-sums equal to m, their girth, and the local action of the vertex-stabilizer. Also, it is shown that the only instance where S_n acts transitively on 2-arcs occurs in the case m = r = 2. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 107–117, 1997     

Judicious partitions of directed graphs

The area of judicious partitioning considers the general family of partitioning problems in which one seeks to optimize several parameters simultaneously, and these problems have been widely studied in various combinatorial contexts. In this paper, we study essentially the most fundamental judicious partitioning problem for directed graphs, which naturally extends the classical Max Cut problem to this setting: we seek bipartitions in which many edges cross in each direction. It is easy to see that a minimum outdegree condition is required in order for the problem to be nontrivial, and we prove that every directed graph with m edges and minimum outdegree at least two admits a bipartition in which at least edges cross in each direction. We also prove that if the minimum outdegree is at least three, then the constant can be increased to . If the minimum outdegree tends to infinity with n, then the constant increases to . All of these constants are best‐possible, and provide asymptotic answers to a question of Alex Scott. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 147–170, 2016     

Fair reception and Vizing's conjecture

In this paper we introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs G with a fair reception of size γ(G) satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well‐known result of Barcalkin and German concerning decomposable graphs. Combining our concept with a result of Aharoni, Berger and Ziv, we obtain an alternative proof of the theorem of Aharoni and Szabó that chordal graphs satisfy Vizing's conjecture. A new infinite family of graphs that satisfy Vizing's conjecture is also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 45‐54, 2009     

The Erd s-Sós conjecture for graphs of girth 5

We prove that every graph of girth at least 5 with minimum degree δ k/2 contains every tree with k edges, whose maximum degree does not exceed the maximum degree of the graph. An immediate consequence is that the famous Erd s-Sós Conjecture, saying that every graph of order n with more than n(k − 1)/2 edges contains every tree with k edges, is true for graphs of girth at least 5.     

Queue layouts of iterated line directed graphs

In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph.We present upper and lower bounds on the queuenumber of an iterated line directed graph L^k(G) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of L^k(G), it is shown that for any fixed directed graph G, L^k(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in L^k(G). These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd.     

Rooted directed path graphs are leaf powers

Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph G=(V,E) is called k-leaf power if it admits a k-leaf root, i.e., a tree T with leaves V such that uv is an edge in G if and only if the distance between u and v in T is at most k. Moroever, a graph is simply called leaf power if it is a k-leaf power for some k∈N. This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a k-leaf power.We show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, we provide the largest currently known proper subclass of leaf powers, i.e, the class of rooted directed path graphs.Subsequently, we study the leaf rank problem, the algorithmic challenge of determining the minimum k for which a given graph is a k-leaf power. Firstly, we give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, we use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, we provide efficient algorithms to compute 2|V|-leaf roots for given ptolemaic or (unit) interval graphs G=(V,E).