Discrete Geometry, Combinatorics and Graph Theory

Frontmatter

Infinite Series of Generalized Gosper Space Filling Curves

Abstract

We report on computer search for generalized Gosper curve for 37 < N < 61, where N is the degree of the generalized Gosper curve. From the results of the computer search and some geometrical insight, we conjecture that the degree N satisfies N = 6n + 1. We investigate the existence of infinite series of generalized Gosper curves. We show how to generate these series and introduce two new methods, the ‘decomposition method’ and the ‘modified layer method’.

Jin Akiyama, Hiroshi Fukuda, Hiro Ito, Gisaku Nakamura

Contractible Edges in a k-Connected Graph

Abstract

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. Some results concerning k-contractible edges in a k-connected graph are presented.

Kiyoshi Ando

An Implicit Weighted Degree Condition for Heavy Cycles in Weighted Graphs

Abstract

Let G be a 2-connected weighted graph and m a nonnegative number. As introduced by Li as the weighted analogue of a concept due to Zhu et al, we use id ^w (v) to denote the implicit weighted degree of a vertex v in G. In this paper we prove that G contains either a Hamilton cycle or a cycle of weight at least m, if the following two conditions are satisfied: (1) max {id ^w (u), id ^w (v)} ≥ m/2 for each pair of nonadjacent vertices u and v that are vertices of an induced claw or an induced modified claw of G; (2) In each induced claw, each induced modified claw and each induced P ₄ of G, all the edges have the same weight. This is a common generalization of several previous results on the existence of long cycles in unweighted graphs and heavy cycles in weighted graphs.

Bing Chen, Shenggui Zhang, T. C. Edwin Cheng

On the Choice Numbers of Some Complete Multipartite Graphs

Abstract

For every vertex v in a graph G, let L(v) denote a list of colors assigned to v. A list coloring is a proper coloring f such that f(v) ∈ L(v) for all v. A graph is k-choosable if it admits a list coloring for every list assignment L with |L(v)| = k. The choice number of G is the minimum k such that G is k-choosable. We generalize a result (of [4]) concerning the choice numbers of complete bipartite graphs and prove some uniqueness results concerning the list colorability of the complete (k + 1)-partite graph K _{n, ..., n, m}. Using these, we determine the choice numbers for some complete multipartite graphs K _{n, ..., n, m}. As a byproduct, we classify (i) completely those complete tripartite graphs K _{2, 2, m} and (ii) almost completely those complete bipartite graphs K _{n, m} (for n ≤ 6) according to their choice numbers.

G. L. Chia, V. L. Chia

On Convex Quadrangulations of Point Sets on the Plane

Abstract

Let P _n be a set of n points on the plane in general position, n ≥ 4. A convex quadrangulation of P _n is a partitioning of the convex hull \(\mathit{Conv}(P_n)\) of P _n into a set of quadrilaterals such that their vertices are elements of P _n , and no element of P _n lies in the interior of any quadrilateral. It is straightforward to see that if P admits a quadrilaterization, its convex hull must have an even number of vertices. In [6] it was proved that if the convex hull of P _n has an even number of points, then by adding at most \(\frac{3n}{2}\) Steiner points in the interior of its convex hull, we can always obtain a point set that admits a convex quadrangulation. The authors also show that \(\frac{n}{4}\) Steiner points are sometimes necessary. In this paper we show how to improve the upper and lower bounds of [6] to \(\frac{4n}{5}+2\) and to \(\frac{n}{3}\) respectively. In fact, in this paper we prove an upper bound of n, and with a long and unenlightening case analysis (over fifty cases!) we can improve the upper bound to \(\frac{4n}{5}+2\), for details see [9].

V. M. Heredia, J. Urrutia

Sufficient Conditions for the Existence of Perfect Heterochromatic Matchings in Colored Graphs

Abstract

Let G = (V, E) be an edge-colored graph. A matching of G is called heterochromatic if its any two edges have different colors. Unlike uncolored matchings for which the maximum matching problem is solvable in polynomial time, the maximum heterochromatic matching problem is NP-complete. This means that to find both sufficient and necessary good conditions for the existence of perfect heterochromatic matchings should be not easy. In this paper, we obtain sufficient conditions of Hall-type and Tutte-type for the existence of perfect heterochromatic matchings in colored bipartite graphs and general colored graphs. We also obtain a sufficient and necessary condition of Berge-type to verify if a heterochromatic matching M of G is maximum.

Lin Hu, Xueliang Li

Impossibility of Transformation of Vertex Labeled Simple Graphs Preserving the Cut-Size Order

Abstract

Three partial orders, cut-size order, length order, and operation order, defined between labeled graphs with the same number of vertices are known to be equivalent. From the equivalence, G precedes G′ in the order means that there is a sequence of cross-operations transforming G into G′. However, even if both graphs are simple, non-simple graphs may appear on the way of the transformation. If both graphs have the same number of edges, we conjecture that there is a sequence in which only simple graphs appear. But for graphs having different number of edges, there is a counter example. That is, there is a pair of simple graphs G and G′ such that G precedes G′ in the order and G can not be transformed into G′ by using only simple graphs. Thus we must introduce other operations than cross-operation for transforming them by using only simple graphs. Then we naturally reach to a question: is there a sufficient set of operations for this purpose? For this problem, this paper shows a negative result that there is no such finite set of operations.

Hiro Ito

A Neighborhood Condition for Graphs to Have [a, b]-Factors III

Abstract

Let a, b, k, and m be positive integers such that 1 ≤ a < b and 2 ≤ k ≤ (b + 1 − m)/a. Let G = (V(G), E(G)) be a graph of order |G|. Suppose that |G| > (a + b)(k(a + b − 1) − 1)/b and |N _G (x ₁) ∪ N _G (x ₂) ∪ ⋯ ∪ N _G (x _k )| ≥ a|G|/(a + b) for every independent set { x ₁, x ₂, ..., x _k } ⊆ V(G). Then for any subgraph H of G with m edges and δ(G − E(H)) ≥ a, G has an [a, b]-factor F such that E(H) ∩ E(F) = ∅. This result is best possible in some sense and it is an extension of the result of Matsuda (Discrete Mathematics 224 (2000) 289–292).

M. Kano, Haruhide Matsuda

General Balanced Subdivision of Two Sets of Points in the Plane

Abstract

Let R and B be two disjoint sets of red points and blue points, respectively, in the plane such that no three points of R ∪ B are co-linear. Suppose ag ≤ |R| ≤ (a + 1)g, bg ≤ |B| ≤ (b + 1)g. Then without loss of generality, we can express |R| = a(g ₁ + g ₂) + (a + 1)g ₃,  |B| = bg ₁ + (b + 1)(g ₂ + g ₃), where g = g ₁ + g ₂ + g ₃, g ₁ ≥ 0, g ₂ ≥ 0, g ₃ ≥ 0 and g ₁ + g ₂ + g ₃ ≥ 1. We show that the plane can be subdivided into g disjoint convex polygons \(X_{1}\cup \cdots \cup X_{g_1}\cup Y_{1}\cup \cdots \cup Y_{g_2}\cup Z_{1}\cup \cdots \cup Z_{g_3}\) such that every X _i contains a red points and b blue points, every Y _i contains a red points and b + 1 blue points and every Z _i contains a + 1 red points and b + 1 blue points.

M. Kano, Miyuki Uno

Coverage Problem of Wireless Sensor Networks

Abstract

In this paper we study the limiting achievable coverage problems of sensor networks. For the sensor networks with uniform distributions we obtain a complete characterization of the coverage probability. For the sensor networks with non-uniform distributions, we derive two different necessary and sufficient conditions respectively in the situations that the density function achieves its minimum value on a set with positive Lebesgue measure or at finitely many points. We propose also an economical scheme for the coverage of sensor networks with empirical distributions.

G. L. Lan, Z. M. Ma, S. S. Sun

Some Topics on Edge-Coloring

Abstract

In this paper some new results on edge coloring of graphs are introduced. This paper deals mainly with edge cover coloring, g-edge cover coloring, (g, f)-coloring and equitable edge coloring. Some new problems and conjectures are presented.

Guizhen Liu, Changqing Xu

Hamiltonicity of Complements of Total Graphs

Abstract

For a graph G, the total graph T(G) of G is the graph with vertex set V(G) ∪ E(G) in which the vertices x and y are joined by an edge if x and y are adjacent or incident in G. In this paper, we show that the complement of total graph T(G) of a simple graph G is hamiltonian if and only if G is not isomorphic to any graph in {K _{1, r} | r ≥ 1} ∪ {K _{1, s}  + K ₁| s ≥ 1} ∪ {K _{1, t}  + e| t ≥ 2} ∪ {K ₂ + 2K ₁, K ₃ + ,K ₁, K ₃ + 2K ₁, K ₄}.

Guoyan Ma, Baoyindureng Wu

Isolated Toughness and Existence of f-Factors

Abstract

Let G be a graph with vertex set V(G) and edge set E(G). The isolated toughness of G is defined as I(G) = min{|S|/i(G − S) | S ⊆ V(G), i(G − S) ≥ 2} if G is not complete; otherwise, set I(G) = |V(G)| − 1. Let f and g be two nonnegative integer-valued functions defined on V(G) satisfying a ≤ g(x) ≤ f(x) ≤ b . The purpose in this paper are to present sufficient conditions in terms of the isolated toughness and the minimum degree for graphs to have f-factors and (g, f)-factors (g < f). If g(x) ≡ a < b ≡ f(x), the conditions can be weakened.

Yinghong Ma, Qinglin Yu

A Note on the Integrity of Middle Graphs

Abstract

The integrity I(G) of a noncomplete connected graph G is a measure of network invulnerability and is defined by I(G) =  min {|S| + m(G − S)}, where S and m(G − S) denote the the subset of V and the order of the largest component of G − S, respectively. In this paper, we determine the integrity and some other parameters of middle graphs of some classes of graphs.

Aygul Mamut, Elkin Vumar

Indecomposable Coverings

Abstract

We prove that for every k > 1, there exist k-fold coverings of the plane (1) with strips, (2) with axis-parallel rectangles, and (3) with homothets of any fixed concave quadrilateral, that cannot be decomposed into two coverings. We also construct, for every k > 1, a set of points P and a family of disks \(\cal D\) in the plane, each containing at least k elements of P, such that no matter how we color the points of P with two colors, there exists a disk \(D\in{\cal D}\), all of whose points are of the same color.

János Pach, Gábor Tardos, Géza Tóth

The Decycling Number of Cubic Planar Graphs

Abstract

Bau and Beineke [2] asked the following questions:

1

Which cubic graphs G of order 2n have decycling number \(\phi(G)= \lceil\frac{n+1}{2}\rceil\)?

 

1

Which cubic planar graphs G of order 2n have decycling number \(\phi(G)=\lceil\frac{n+1}{2}\rceil\)?

 

We answered the first question in [10]. In this paper we prove that if \({{\cal{P}}}(3^{2n})\) is the class of all connected cubic planar graphs of order 2n and \({\phi\left({\cal{P}}(3^{2n})\right)} = \left\{{\phi(G)\colon G\in {\cal{P}}}(3^{2n})\right\}\), then there exist integers a _n and b _n such that there exists a graph \(G \in {\cal{P}}(3^{2n})\) with φ(G) = c if and only if c is an integer satisfying a _n  ≤ c ≤ b _n . We also find all corresponding integers a _n and b _n . In addition, we prove that if \({{\cal{P}}\left(3^{2n};\, \phi =\lceil\frac{n+1}{2}\rceil\right)}\) is the class of all connected cubic planar graphs of order 2n with decycling number \(\lceil\frac{n+1}{2}\rceil\) and \(G_1,\, G_2 \in {\cal{P}}\left(3^{2n};\, \phi =\lceil\frac{n+1}{2}\rceil\right)\), then there exists a sequence of switchings σ ₁, σ ₂, ..., σ _t such that for every i = 1, 2, ..., t − 1, \(G_1^{\sigma_1\sigma_2\cdots\sigma_i} \in {\cal{P}}\left(3^{2n};\, \phi =\lceil\frac{n+1}{2}\rceil\right)\) and \(G_2 = G_1^{\sigma_1\sigma_2\cdots\sigma_t}\).

Narong Punnim

Quasilocally Connected, Almost Locally Connected Or Triangularly Connected Claw-Free Graphs

Abstract

The definitions of quasilocally connected graphs, almost locally connected graphs and triangularly connected graphs are introduced by Zhang, Teng and Lai et al. They are all different extensions of locally connected graphs. Many known results on the condition of local connectivity have been extended to these weaker conditions mentioned above. In this paper, we study the relations among these different conditions. In particular, we prove that every triangularly connected claw-free graph without isolated vertices is also quasilocally connected claw-free.

Xiaoying Qu, Houyuan Lin

Rotational Steiner Ratio Problem Under Uniform Orientation Metrics

Abstract

Let P be a set of n points in a metric space. A Steiner Minimal Tree (SMT) on P is a shortest network interconnecting P while a Minimum Spanning Tree (MST) is a shortest network interconnecting P with all edges between points of P. The Steiner ratio is the infimum over P of ratio of the length of SMT over that of MST. Steiner ratio problem is to determine the value of the ratio. In this paper we consider the Steiner ratio problem in uniform orientation metrics, which find important applications in VLSI design. Our study is based on the fact that lengths of MSTs and SMTs could be reduced through properly rotating coordinate systems without increasing the number of orientation directions. We obtain the Steiner ratios with |P| = 3 when rotation is allowed and some bounds of Steiner ratios for general case.

Songpu Shang, Xiaodong Hu, Tong Jing

Two Classes of Simple MCD Graphs

Abstract

Let S _n be the set of simple graphs on n vertices in which no two cycles have the same length. A graph G in S _n is called a simple maximum cycle-distributed graph (simple MCD graph) if there exists no graph G′ in S _n with |E(G′)| > |E(G)|. A planar graph G is called a generalized polygon path (GPP) if G ^* formed by the following method is a path: corresponding to each interior face f of \(\tilde G\) (\(\tilde G\) is a plane graph of G) there is a vertex f ^* of G ^*; two vertices f ^* and g ^* are adjacent in G ^* if and only if the intersection of the boundaries of the corresponding interior faces of \(\tilde G\) is a simple path of \(\tilde G\). In this paper, we prove that there exists a simple MCD graph on n vertices such that it is a 2-connected graph being not a GPP if and only if n ∈ {10, 11, 14, 15, 16, 21, 22}. We also prove that, by discussing all the natural numbers except for 75 natural numbers, there are exactly 18 natural numbers, for each n of which, there exists a simple MCD graph on n vertices such that it is a 2-connected graph.

Yong-Bing Shi, Yin-Cai Tang, Hua Tang, Ling-Liu Gong, Li Xu

Core Stability of Flow Games

Abstract

In this paper, we study the problem of core stability for flow games, introduced by Kalai and Zemel (1982), which arises from the profit distribution problem related to the maximum flow in networks. Based on the characterization of dummy arc (i.e., the arc which satisfies that deleting it does not change the value of maximum flow in the network), we prove that the flow game defined on a simple network has the stable core if and only if there is no dummy arc in the network. We also show that the core largeness, the extendability and the exactness of flow games are equivalent conditions, which strictly imply the stability of the core.

Xiaoxun Sun, Qizhi Fang

The (Adjacent) Vertex-Distinguishing Total Coloring of the Mycielski Graphs and the Cartesian Product Graphs

Abstract

The graph obtained by the famous Mycielski’s construction is called the Mycielski graph. This paper focuses on the relation between the basic graphs and two classes of constructed graphs on the (adjacent) vertex-distinguishing total coloring. And some sufficient conditions with which the Mycielski graphs and the Cartesian product graphs satisfy the adjacent vertex-distinguishing total coloring conjecture are given.

Yanli Sun, Lei Sun

Three Classes of Bipartite Integral Graphs

Abstract

A graph G is called integral if all zeros of its characteristic polynomial P(G, x) are integers. In this paper, the bipartite graphs K _{p, q(t)}, K _{p(s), q(t)} and K _{p, q} ≡ K _{q, r} are defined. We shall derive their characteristic polynomials from matrix theory. We also obtain their sufficient and necessary conditions for the three classes of graphs to be integral. These results generalize some results of Balińska et al. The discovery of these integral graphs is a new contribution to the search of integral graphs.

Ligong Wang, Hao Sun

Reconfirmation of Two Results on Disjoint Empty Convex Polygons

Abstract

For k ≥ 3, let m(k,k + 1) be the smallest integer such that any set of m(k,k + 1) points in the plane, no three collinear, contains two different subsets Q ₁ and Q ₂, such that CH(Q ₁) is an empty convex k −gon, CH(Q ₂) is an empty convex (k + 1) −gon, and CH(Q ₁) ∩ CH(Q ₂) = ∅, where CH stands for the convex hull. In this paper, we revisit the case of k = 3 and k = 4, and provide new proofs.

Liping Wu, Ren Ding

The Binding Number of a Digraph

Abstract

Caccetta-Häggkvist’s Conjecture discusses the relation between the girth g(D) of a digraph D and the minimum outdegree δ ⁺(D) of D. The special case when g(D) = 3 has lately attracted wide attention. For an undirected graph G, the binding number \(bind(G)\geq \frac 3 2\) is a sufficient condition for G to have a triangle (cycle with length 3). In this paper we generalize the concept of binding numbers to digraphs and give some corresponding results. In particular, the value range of binding numbers is given, and the existence of digraphs with a given binding number is confirmed. By using the binding number of a digraph we give a condition that guarantees the existence of a directed triangle in the digraph. The relationship between binding number and connectivity is also discussed.

Genjiu Xu, Xueliang Li, Shenggui Zhang

The Kauffman Bracket Polynomial of Links and Universal Signed Plane Graph

Abstract

In this paper we show that a list of chain polynomials of 6 graphs are sufficient to give all the chain polynomials of signed plane graphs with cyclomatic number 1 − 5 by special parametrization. Using this result the Kauffman bracket polynomials of 801 knots and 1424 links with crossing number no more than 11 can be obtained in a unify way.

Weiling Yang, Fuji Zhang

Fractional Vertex Arboricity of Graphs

Abstract

The vertex arboricity va(G) of a graph G is the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces an acyclic subgraph. The fractional version of vertex arboricity is introduced in this paper. We determine fractional vertex arboricity for several classes of graphs, e.g., complete multipartite graphs, cycles, integer distance graphs, prisms and Peterson graph.

Qinglin Yu, Liancui Zuo

Fitting Triangles into Rectangles

Abstract

A figure F and a target set T are given in the plane. We say that the figure F fits in the target T, or, equivalently, the target T covers the figure F, when there is a rigid motion μ (an isometry of the plane) so that μ(F) ⊆ T, i.e., if T has a subset congruent to F. In this paper we find necessary and sufficient conditions for a triangle with sides a, b, c to fit into a rectangle with sides u and v.

Liping Yuan, Yevgenya Movshovich, Ren Ding

Regular Coronoids and Ear Decompositions of Plane Elementary Bipartite Graphs

Abstract

A connected bipartite graph is called elementary (or normal) if its every edge is contained in some perfect matching. In rho classification of coronoids due to Cyvin et al., normal coronoids are divided into two types: regular and half essentially disconnected. A coronoid is called regular if it can be generated from a single hexagon by a series of normal additions of hexagons (modes L ₁, L ₃ or L ₅) plus corona condensations of hexagons of modes L ₂ or A ₂. Chen and Zhang (1997) gave a complete characterization: A coronoid is regular if and only if it has a perfect matching M such that the boundaries of non-hexagon faces are all M-alternating cycles. In this article, a general concept for the regular addition of an allowed face is proposed and the above result is extended to a plane elementary bipartite graph some specified faces of which are forbidden by applying recently developed matching theory. As its corollary, we give an equivalent definition of regular coronoids as a special ear decomposition.

Heping Zhang

On the Upper Chromatic Numbers of Mixed Interval Hypertrees

Abstract

A mixed hypergraph consists of a finite set and two families of subsets: C-edges and D-edges. In a coloring, every C-edge has at least two vertices of the same color, and every D-edge has at least two vertices colored differently. The maximum and minimum numbers of colors are called the lower and upper chromatic numbers, respectively. A mixed hypergraph \({\cal H}\) with vertex set X, C-edge set \({\cal C}\) and D-edge set \({\cal D}\) is usually denoted by \({\cal H}=(X,\, {\cal C},\, {\cal D})\). E. Bulgaru and V. Voloshin proved that \(\overline{\chi}({\cal H})=|X|-s({\cal H})\) holds for any mixed interval hypergraph ([3]), where \(s({\cal H})\) is the sieve number of \({\cal H}\). In this paper we prove that \(\overline{\chi}({\cal H})=|X|-s({\cal H})\) also holds for any mixed interval hypertree.

Ping Zhao, Kefeng Diao

Note on Characterization of Uniquely 3-List Colorable Complete Multipartite Graphs

Abstract

Let G be a graph and suppose that for each vertex v of G, there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. M. Ghebleh and E. S. Mahmoodian characterized uniquely 3-List colorable complete multipartite graphs except for nine graphs. Recently, except for graph K _2,3,4, the other eight graphs were shown not to be uniquely 3-list colorable by W. He and Y. Shen, etc. In this paper, it is proved that K _2,3,4 is not uniquely 3-list colorable, and then the uniquely 3-list colorable complete multipartite graphs are characterized completely.

Yongqiang Zhao, Wenjie He, Yufa Shen, Yanning Wang

Backmatter