平面图书式嵌入综述

图书式嵌入问题主要起源于大型集成电路(VLSI)设计和多层线路板印刷(PCBs)设计等诸多领域,有广泛的应用价值.图的书式嵌入是将图的点集排在一条直线上(书脊)且将边嵌入到以书脊为边界的半平面上(页)使得同页中的边互不相交.其研究的一个重要参数是页数(满足条件所需的最小页数),该问题是NP-困难的.本文主要综述平面图书式嵌入问题的相关研究.     

Embedding Generalized Petersen Graph in Books

A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph $G$ can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.     

On a straight-line embedding problem of graphs

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane in general position. A straight-line embedding of G onto P is an embedding of G onto whose images of vertices are distinct points in P and whose images of edges are (straight) line segments. In this paper, we classify into five classes those pairs of G and v such that for any P and any p P, G has a straight-line embedding onto P which maps v to p. We then show that all graphs in three of the classes indeed have such an embedding. This result gives a solution to a generalized version of the rooted-tree embedding problem raised by M. Perles.     

Random packing by ρ-connected ρ-regular graphs

A graph G is packable by the graph F if its edges can be partitioned into copies of F. If deleting the edges of any F-packable subgraph from G leaves an F-packable graph, then G is randomly F-packable. If G is F-packable but not randomly F-packable then G is F-forbidden. The minimal F-forbidden graphs provide a characterization of randomly F-packable graphs. We show that for each ρ-connected ρ-regular graph F with ρ > 1, there is a set (F) of minimal F-forbidden graphs of a simple form, such that any other minimal F-forbidden graph can be obtained from a graph in (F) by a process of identifying vertices and removing copies of F. When F is a connected strongly edge-transitive graph having more than one edge (such as a cycle or hypercube), there is only one graph in (F).     

Pagenumber of complete bipartite graphs

Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t(G) (also called book thickness) is the minimum number of pages in a book embedding of G. We present a general construction showing t(K_m,n) ? ?(m + 2n)/4?, which we conjecture optimal. We prove a result suggesting this is optimal for m ? 2n ? 3. For the most difficult case m = n, we consider vertex permutations that are regular, i.e., place vertices from each partite set into runs of equal size. Book embeddings with such orderings require ?(7n ? 2)/9? pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.     

Subgraph distances in graphs defined by edge transfers

For two edge-induced subgraphs F and H of the same size in a graph G, the subgraph H can be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uv ε E(F), wx ε E(G) - E(F), and H = F - uv + wx. The subgraph F is j-transformed into H if H can be obtained from F by a sequence of edge jumps. Necessary and sufficient conditions are presented for a graph G to have the property that every edge-induced subgraph of a fixed size in G can be j-transformed into every other edge-induced subgraph of that size. The minimum number of edge jumps required to transform one subgraph into another is called the jump distance. This distance is a metric and can be modeled by a graph. The jump graph J(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of J(G) are adjacent if and only if the corresponding edges of G are independent. For a given graph G, we consider the sequence {{J^k(G)}} of iterated jump graphs and classify each graph as having a convergent, divergent, or terminating sequence.     

Graph rigidity via Euclidean distance matrices

Let G=(V,E,ω) be an incomplete graph with node set V, edge set E, and nonnegative weights ω_ij's on the edges. Let each edge (v_i,v_j) be viewed as a rigid bar, of length ω_ij, which can rotate freely around its end nodes. A realization of a graph G is an assignment of coordinates, in some Euclidean space, to each node of G. In this paper, we consider the problem of determining whether or not a given realization of a graph G is rigid. We show that each realization of G can be epresented as a point in a compact convex set ; and that a generic realization of G is rigid if and only if its corresponding point is a vertex of Ω, i.e., an extreme point with full-dimensional normal cone.     

Magic Labeling of Disjoint Union Graphs

Let G be a graph with vertex set V (G), edge set E(G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …,|E(G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to (1+|E(G)|)/2·d(v), where d(v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V (G),|{e:e ∈ E_v, f(e) ≤ Δ/2}|=|{e:e ∈ E_v, f(e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2m + 1)G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results.     

Wings and perfect graphs

An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in G. A graph G is saturated if G is isomorphic to W(G). A star-cutset in a graph G is a non-empty set of vertices such that G — C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. V. Chvátal proposed to call a graph unbreakable if neither G nor its complement contain a star-cutset. We establish several properties of unbreakable graphs using the notions of wings and saturation. In particular, we obtain seven equivalent versions of the Strong Perfect Graph Conjecture.     

带松弛条件的图的强边着色

给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次.图G的(s,t)-松弛强边着色指数,记作x'(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值.在图G中...     

Primitive graphs with given exponents and minimum number of edges

A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even.     

Extending matchings in planar graphs V

A graph G on at least 2n + 2 vertices in n-extendable if every set of n independent edges extends to (i.e., is a subset of) a perfect matching in G. It is known that no planar graph is 3-extendable. In the present paper we continue to study 2-extendability in the plane. Suppose independent edges e₁ and e₂ are such that the removal of their endvertices leaves at least one odd component C_o. The subgraph G[V(C_o) V(e₁) V(e₂)] is called a generalized butterfly (or gbutterfly). Clearly, a 2-extendable graph can contain no gbutterfly. The converse, however, is false.

We improve upon a previous result by proving that if G is 4-connected, locally connected and planar with an even number of vertices and has no gbutterfly, it is 2-extendable. Sharpness with respect to the various hypotheses of this result is discussed.     

Connectivity of generalized prisms over G

The problem of building larger graphs with a given graph as an induced subgraph is one which can arise in various applications and in particular can be important when constructing large communications networks from smaller ones. What one can conclude from this paper is that generalized prisms over G may provide an important such construction because the connectivity of the newly created graph is larger than that of the original (connected) graph, regardless of the permutation used.

For a graph G with vertices labeled 1,2,…, n and a permutation in S_n, the generalized prisms over G, (G) (also called a permutation graph), consists of two copies of G, say G_x and G_y, along with the edges (x_i, y_(i), for 1≤i≤n. The purpose of this paper is to examine the connectivity of generalized prisms over G. In particular, upper and lower bounds are found. Also, the connectivity and edge-connectivity are determined for generalized prisms over trees, cycles, wheels, n-cubes, complete graphs, and complete bipartite graphs. Finally, the connectivity of the generalized prism over G, (G), is determined for all in the automorphism group of G.     

Some results on characterizing the edges of connected graphs with a given domination number

A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m₁ (G, D) denote the number of edges that have neither endpoint in D, and let m₂ (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m₁ (G, D), m₂ (G, D)) can attain for connected graphs having a given domination number.     

A Note on Strong Edge Coloring of Sparse Graphs

A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ'_s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2 k. Yang and Zhu [J. Graph Theory, 83, 334–339(2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4 kΔ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤ 4 kΔ-2 k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most(4 k-1)Δ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤(4 k-1)Δ-2 k + 1.     

图的区间边着色的收缩图方法

图G的一个用了颜色1,2,…,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的,且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作■.对图G∈■,使得G有一个区间t-着色的t的最小值和最大值分别记作ω(G)和W(G).现给出了图的区间着色的收缩图方法.利用此方法,我们对双圈图G∈■,证明了ω(G)=△(G)或△(G)+1,并且完全确定了ω(G)=△(G)及ω(G)=△(G)+1的双圈图类.     

6-圈至多含一弦平面图的线性荫度

线性森林是指每个连通分支都是路的图.图G的线性荫度la(G)等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了,若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图,则la(G)=「(△(G))/2」.     

Bipartite double cover and perfect 2-matching covered graph with its algorithm

Let B(G) denote the bipartite double cover of a non-bipartite graph G with v≥2 vertices and ? edges. We prove that G is a perfect 2-matching covered graph if and only if B(G) is a 1-extendable graph. Furthermore, we prove that B(G) is a minimally 1-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy ∈ E(G), there is an independent set S in G such that |Γ_G(S)| = |S| + 1, x ∈S and |Γ_G-xy(S) | = |S|. Then, we construct a digraph D from B(G) or G and show that D is a strongly connected digraph if and only if G is a perfect 2-matching covered graph. So we design an algorithm in O(v?) time that determines whether G is a perfect 2-matching covered graph or not.