关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

Graph pegging numbers

In graph pegging, we view each vertex of a graph as a hole into which a peg can be placed, with checker-like “pegging moves” allowed. Motivated by well-studied questions in graph pebbling, we introduce two pegging quantities. The pegging number (respectively, the optimal pegging number) of a graph is the minimum number of pegs such that for every (respectively, some) distribution of that many pegs on the graph, any vertex can be reached by a sequence of pegging moves. We prove several basic properties of pegging and analyze the pegging number and optimal pegging number of several classes of graphs, including paths, cycles, products with complete graphs, hypercubes, and graphs of small diameter.     

On the Hadwiger's conjecture for graph products

The Hadwiger number η(G) of a graph G is the largest integer h such that the complete graph on h nodes K_h is a minor of G. Equivalently, η(G) is the largest integer such that any graph on at most η(G) nodes is a minor of G. The Hadwiger's conjecture states that for any graph G, η(G)?χ(G), where χ(G) is the chromatic number of G. It is well-known that for any connected undirected graph G, there exists a unique prime factorization with respect to Cartesian graph products. If the unique prime factorization of G is given as G₁□G₂□?□G_k, where each G_i is prime, then we say that the product dimension of G is k. Such a factorization can be computed efficiently.In this paper, we study the Hadwiger's conjecture for graphs in terms of their prime factorization. We show that the Hadwiger's conjecture is true for a graph G if the product dimension of G is at least . In fact, it is enough for G to have a connected graph M as a minor whose product dimension is at least , for G to satisfy the Hadwiger's conjecture. We show also that if a graph G is isomorphic to F^d for some F, then η(G)?χ(G)^{⌊(d-1)/2⌋}, and thus G satisfies the Hadwiger's conjecture when d?3. For sufficiently large d, our lower bound is exponentially higher than what is implied by the Hadwiger's conjecture.Our approach also yields (almost) sharp lower bounds for the Hadwiger number of well-known graph products like d-dimensional hypercubes, Hamming graphs and the d-dimensional grids. In particular, we show that for the d-dimensional hypercube H_d, . We also derive similar bounds for G^d for almost all G with n nodes and at least edges.     

Generating Nonisomorphic Quadrangular Embeddings of a Complete Graph

We construct (resp. ) index one current graphs with current group such that the current graphs have different underlying graphs and generate nonisomorphic orientable (resp. nonorientable) quadrangular embeddings of the complete graph , (resp. ).     

Graph eigenspaces of small codimension

For a given positive integer t there are only finitely many graphs with an eigenvalue μ{−1,0} such that the eigenspace of μ has codimension t. The graphs for which t5 are identified.     

Graph family operations

In previous papers, Catlin introduced four functions, denoted , , , and , between sets of finite graphs. These functions proved to be very useful in establishing properties of several classes of graphs, including supereulerian graphs and graphs with nowhere zero k-flows for a fixed integer k3. Unfortunately, a subtle error caused several theorems previously published in Catlin (Discrete Math. 160 (1996) 67–80) to be incorrect. In this paper we correct those errors and further explore the relations between these functions, showing that there is a sort of duality between them and that they act as inverses of one another on certain sets of graphs.     

Graph drawings with few slopes

The slope-number of a graph G is the minimum number of distinct edge slopes in a straight-line drawing of G in the plane. We prove that for Δ5 and all large n, there is a Δ-regular n-vertex graph with slope-number at least . This is the best known lower bound on the slope-number of a graph with bounded degree. We prove upper and lower bounds on the slope-number of complete bipartite graphs. We prove a general upper bound on the slope-number of an arbitrary graph in terms of its bandwidth. It follows that the slope-number of interval graphs, cocomparability graphs, and AT-free graphs is at most a function of the maximum degree. We prove that graphs of bounded degree and bounded treewidth have slope-number at most . Finally we prove that every graph has a drawing with one bend per edge, in which the number of slopes is at most one more than the maximum degree. In a companion paper, planar drawings of graphs with few slopes are also considered.     

A proof of the rooted tree alternative conjecture

Bonato and Tardif [A. Bonato, C. Tardif, Mutually embeddable graphs and the tree alternative conjecture, J. Combinatorial Theory, Series B 96 (2006), 874-880] conjectured that the number of isomorphism classes of trees mutually embeddable with a given tree T is either 1 or infinite. We prove the analogue of their conjecture for rooted trees. We also make some progress towards the original conjecture for locally finite trees and state some new conjectures.     

Minors in Expanding Graphs

We propose a unifying framework for studying extremal problems related to graph minors. This framework relates the existence of a large minor in a given graph to its expansion properties. We then apply the developed framework to several extremal problems and prove in particular that: (a) Every -free graph G with average degree r ( are constants) contains a minor with average degree , for some constant ; (b) Every C_2k-free graph G with average degree r (k ≥ 2 is a constant) contains a minor with average degree , for some constant c = c(k) > 0. We also derive explicit lower bounds on the minor density in random, pseudo-random and expanding graphs. Received: March 2008, Accepted: May 2008     

Counterexamples to Grötzsch-Sachs-Koester's conjecture

Let G be a 4-regular planar graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly on cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Grötzsch-Sachs-Koester's conjecture states that if the cycles of G can be partitioned into four classes, such that two cycles in the same classes are disjoint, G is vertex 3-colorable. In this note, the conjecture is disproved.     

Graph parameters measuring neighbourhoods in graphs—Bounds and applications

The neighbourhood-width of a graph G=(V,E) is introduced in [F. Gurski, Linear layouts measuring neighbourhoods in graphs, Discrete Math. 306 (15) (2006) 1637-1650.] as the smallest integer k such that there is a linear layout ?:V→{1,…,|V|} such that for every 1?i<|V| the vertices u with ?(u)?i can be divided into at most k subsets each members having the same neighbours with respect to the vertices v with ?(v)>i.In this paper we show first bounds for the neighbourhood-width of general graphs, caterpillars, trees and grid graphs and give applications of the layout parameter neighbourhood-width in graph drawing and VLSI design.     

The edge version of Hadwiger’s conjecture

A well known conjecture of Hadwiger asserts that K_n+1 is the only minor minimal graph of chromatic number greater than n. In this paper, all minor minimal graphs of chromatic index greater than n are determined.     

Graph Coloring and Reverse Mathematics

Improving a theorem of Gasarch and Hirst, we prove that if 2 ≤ k ≤ m < ω, then the following is equivalent to WKL₀ over RCA₀ Every locally k‐colorable graph is m‐colorable.     

基于DNA计算的Hamilton图

DNA computing is a novel method for solving a class of intractable computationalproblems in which the computing can grow exponentially with problem size. Up to now, manyaccomplishments have been achieved to improve its performance and increase its reliability.Hamilton Graph Problem has been solved by means of molecular biology techniques. A smallgraph was encoded in molecules of DNA, and the “operations” of the computation wereperformed with standard protocols and enzymes. This work represents further evidence forthe ability of DNA computing to solve NP-complete search problems.     

Subspace Inclusion Graph of a Vector Space

In this paper, the authors introduce a graph structure, called subspace inclusion graph ?n(𝕍) on a finite dimensional vector space 𝕍 where the vertex set is the collection of nontrivial proper subspaces of a vector space and two vertices are adjacent if one is contained in other. The diameter, girth, clique number, and chromatic number of ?n(𝕍) are studied. It is shown that two subspace inclusion graphs are isomorphic if and only if the base vector spaces are isomorphic. Finally, some properties of subspace inclusion graph are studied when the base field is finite.     

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.     

Distributed computation of virtual coordinates for greedy routing in sensor networks

Sensor networks are emerging as a paradigm for future computing, but pose a number of challenges in the fields of networking and distributed computation. One challenge is to devise a greedy routing protocol—one that routes messages through the network using only information available at a node or its neighbors. Modeling the connectivity graph of a sensor network as a 3-connected planar graph, we describe how to compute on the network in a distributed and local manner a special geometric embedding of the graph. This embedding supports a geometric routing protocol called “greedy routing” based on the “virtual” coordinates of the nodes derived from the embedding.