A study on cyclic bandwidth sum

Suppose G is a graph of p vertices. A proper labeling f of G is a one-to-one mapping f:V(G)→{1,2,…,p}. The cyclic bandwidth sum of G with respect to f is defined by CBS _f (G)=∑ _uv∈E(G)|f(v)−f(u)| _p , where |x| _p =min {|x|,p−|x|}. The cyclic bandwidth sum of G is defined by CBS(G)=min {CBS _f (G): f is a proper labeling of G}. The bandwidth sum of G with respect to f is defined by BS _f (G)=∑ _uv∈E(G)|f(v)−f(u)|. The bandwidth sum of G is defined by BS(G)=min {BS _f (G): f is a proper labeling of G}. In this paper, we give a necessary and sufficient condition for BS(G)=CBS(G), and use this to show that BS(T)=CBS(T) when T is a tree. We also find cyclic bandwidth sums of complete bipartite graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grants NSC91-2115-M-156-001.     

On total weight choosability of graphs

For a graph G with vertex set V and edge set E, a (k,k′)-total list assignment L of G assigns to each vertex v a set L(v) of k real numbers as permissible weights, and assigns to each edge e a set L(e) of k′ real numbers as permissible weights. If for any (k,k′)-total list assignment L of G, there exists a mapping f:V∪E→? such that f(y)∈L(y) for each y∈V∪E, and for any two adjacent vertices u and v, ∑ _y∈N(u) f(uy)+f(u)≠∑ _x∈N(v) f(vx)+f(v), then G is (k,k′)-total weight choosable. It is conjectured by Wong and Zhu that every graph is (2,2)-total weight choosable, and every graph with no isolated edges is (1,3)-total weight choosable. In this paper, it is proven that a graph G obtained from any loopless graph H by subdividing each edge with at least one vertex is (1,3)-total weight choosable and (2,2)-total weight choosable. It is shown that s-degenerate graphs (with s≥2) are (1,2s)-total weight choosable. Hence planar graphs are (1,10)-total weight choosable, and outerplanar graphs are (1,4)-total weight choosable. We also give a combinatorial proof that wheels are (2,2)-total weight choosable, as well as (1,3)-total weight choosable.     

Packing cycles exactly in polynomial time

Let G=(V,E) be an undirected graph in which every vertex v∈V is assigned a nonnegative integer w(v). A w-packing is a collection of cycles (repetition allowed) in G such that every v∈V is contained at most w(v) times by the members of . Let 〈w〉=2|V|+∑ _v∈V ⌈log (w(v)+1)⌉ denote the binary encoding length (input size) of the vector (w(v): v∈V) ^T . We present an efficient algorithm which finds in O(|V|⁸〈w〉²+|V|¹⁴) time a w-packing of maximum cardinality in G provided packing and covering cycles in G satisfy the ℤ₊-max-flow min-cut property.     

Near automorphisms of trees with small total relative displacements

For a permutation f of the vertex set V(G) of a connected graph G, let δ _f (x,y)=|d(x,y)−d(f(x),f(y))|. Define the displacement δ _f (G) of G with respect to f to be the sum of δ _f (x,y) over all unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ _f (G) among the n! permutations f of V(G). In this note, we determine all trees T with π(T)=2 or 4. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.     

Distance graphs on R n with 1-norm

Suppose S is a subset of a metric space X with metric d. For each subset D⊆{d(x,y):x,y∈S,x≠y}, the distance graph G(S,D) is the graph with vertex set S and edge set E(S,D)={xy:x,y∈S,d(x,y)∈D}. The current paper studies distance graphs on the n-space R ₁ ⁿ with 1-norm. In particular, most attention is paid to the subset Z ₁ ⁿ of all lattice points of R ₁ ⁿ . The results obtained include the degrees of vertices, components, and chromatic numbers of these graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grant NSC-94-2115-M-002-015. Taida Institue for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

Minimizing the maximum bump cost in linear extensions of a poset

A linear extension of a poset P=(X,?) is a permutation x ₁,x ₂,…,x _|X| of X such that i<j whenever x _i ?x _j . For a given poset P=(X,?) and a cost function c(x,y) defined on X×X, we want to find a linear extension of P such that maximum cost is as small as possible. For the general case, it is NP-complete. In this paper we consider the linear extension problem with the assumption that c(x,y)=0 whenever x and y are incomparable. First, we prove the discussed problem is polynomially solvable for a special poset. And then, we present a polynomial algorithm to obtain an approximate solution.     

On cubic 2-independent Hamiltonian connected graphs

A graph G=(V,E) is Hamiltonian connected if there exists a Hamiltonian path between any two vertices in G. Let P ₁=(u ₁,u ₂,…,u _|V|) and P ₂=(v ₁,v ₂,…,v _|V|) be any two Hamiltonian paths of G. We say that P ₁ and P ₂ are independent if u ₁=v ₁,u _|V|=v _|V|, and u _i ≠v _i for 1<i<|V|. A cubic graph G is 2-independent Hamiltonian connected if there are two independent Hamiltonian paths between any two different vertices of G. A graph G is 1-Hamiltonian if G−F is Hamiltonian for any F⊆V∪E with |F|=1. A graph G is super 3^*-connected if there exist i internal disjoint paths spanning G for i=1,2,3. It is proved that every super 3^*-connected graph is 1-Hamiltonian. In this paper, we prove that every cubic 2-independent Hamiltonian connected graph is also 1-Hamiltonian. We present some cubic 2-independent Hamiltonian connected graphs that are super 3^*-connected, some cubic 2-independent Hamiltonian connected graphs that are not super 3^*-connected, some super 3^*-connected graphs that are not 2-independent Hamiltonian connected, and some cubic 1-Hamiltonian graphs that are Hamiltonian connected but neither 2-independent Hamiltonian connected nor super 3^*-connected. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 94-2213-E-233-011.     

Three conjectures on the signed cycle domination in graphs

Let G=(V,E) be a graph, a function g:E→{?1,1} is said to be a signed cycle dominating function (SCDF for short) of G if ∑ _e∈E(C) g(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as γ _sc (G)=min{∑ _e∈E(G) g(e)∣g is an SCDF of G}. Xu (Discrete Math. 309:1007–1012, 2009) first researched the signed cycle domination number of graphs and raised the following conjectures: (1) Let G be a maximal planar graphs of order n≥3. Then γ _sc (G)=n?2; (2) For any graph G with δ(G)=3, γ _sc (G)≥1; (3) For any 2-connected graph G, γ _sc (G)≥1. In this paper, we present some results about these conjectures.     

Hardness results and approximation algorithm for total liar’s domination in graphs

In this paper, we initiate the study of total liar’s domination of a graph. A subset L?V of a graph G=(V,E) is called a total liar’s dominating set of G if (i) for all v∈V, |N _G (v)∩L|≥2 and (ii) for every pair u,v∈V of distinct vertices, |(N _G (u)∪N _G (v))∩L|≥3. The total liar’s domination number of a graph G is the cardinality of a minimum total liar’s dominating set of G and is denoted by γ _TLR (G). The Minimum Total Liar’s Domination Problem is to find a total liar’s dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar’s Domination Decision Problem is to check whether G has a total liar’s dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar’s dominating set in a graph. We show that the Total Liar’s Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(lnΔ(G)+1)-approximation algorithm for the Minimum Total Liar’s Domination Problem, where Δ(G) is the maximum degree of the input graph G. We show that Minimum Total Liar’s Domination Problem cannot be approximated within a factor of $(\frac{1}{8}-\epsilon)\ln(|V|)$ for any ?>0, unless NP?DTIME(|V|^loglog|V|). Finally, we show that Minimum Total Liar’s Domination Problem is APX-complete for graphs with bounded degree 4.     

The competition number of a graph with?exactly?two?holes

Given an acyclic digraph D, the competition graph C(D) of D is the graph with the same vertex set as D and two distinct vertices x and y are adjacent in C(D) if and only if there is a vertex v in D such that (x,v) and (y,v) are arcs of D. The competition number κ(G) of a graph G is the least number of isolated vertices that must be added to G to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly two holes is at most three.     

Roman domination on strongly chordal graphs

Given real numbers b≥a>0, an (a,b)-Roman dominating function of a graph G=(V,E) is a function f:V→{0,a,b} such that every vertex v with f(v)=0 has a neighbor u with f(u)=b. An independent/connected/total (a,b)-Roman dominating function is an (a,b)-Roman dominating function f such that {v∈V:f(v)≠0} induces a subgraph without edges/that is connected/without isolated vertices. For a weight function $w{:} V\to\Bbb{R}$ , the weight of f is w(f)=∑ _v∈V w(v)f(v). The weighted (a,b)-Roman domination number $\gamma^{(a,b)}_{R}(G,w)$ is the minimum weight of an (a,b)-Roman dominating function of G. Similarly, we can define the weighted independent (a,b)-Roman domination number $\gamma^{(a,b)}_{Ri}(G,w)$ . In this paper, we first prove that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/independent (a,b)-Roman domination problems are NP-complete for bipartite graphs. We also show that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/weighted independent (a,b)-Roman domination problems are NP-complete for chordal graphs. We then give linear-time algorithms for the weighted (a,b)-Roman domination problem with b≥a>0, and the weighted independent (a,b)-Roman domination problem with 2a≥b≥a>0 on strongly chordal graphs with a strong elimination ordering provided.     

Lower bounds and a tabu search algorithm for the minimum deficiency problem

An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S _v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D _v (G,c) the minimum number of integers which must be added to S _v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ _v∈V D _v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.     

On the union of intermediate nodes of shortest paths

Consider a connected graph G=(V,E). For a pair of nodes u and v, denote by M _uv the set of intermediate nodes of a shortest path between u and v. We are intertested in minimization of the union ? _u,v∈V M _uv . We will show that this problem is NP-hard and cannot have polynomial-time ρlnδ-approximation for 0<ρ<1 unless NP?DTIME(n ^O(loglogn)) where δ is the maximum node degree of input graph. We will also construct a polynomial-time $H(\frac{\delta (\delta -1)}{2})$ -approximation for the problem where H(?) is the harmonic function.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.     

Inference for the Identified Set in Partially Identified Econometric Models

This paper provides computationally intensive, yet feasible methods for inference in a very general class of partially identified econometric models. Let P denote the distribution of the observed data. The class of models we consider is defined by a population objective function Q(θ, P) for θ∈Θ. The point of departure from the classical extremum estimation framework is that it is not assumed that Q(θ, P) has a unique minimizer in the parameter space Θ. The goal may be either to draw inferences about some unknown point in the set of minimizers of the population objective function or to draw inferences about the set of minimizers itself. In this paper, the object of interest is Θ₀(P)=argmin_θ∈ΘQ(θ, P), and so we seek random sets that contain this set with at least some prespecified probability asymptotically. We also consider situations where the object of interest is the image of Θ₀(P) under a known function. Random sets that satisfy the desired coverage property are constructed under weak assumptions. Conditions are provided under which the confidence regions are asymptotically valid not only pointwise in P, but also uniformly in P. We illustrate the use of our methods with an empirical study of the impact of top‐coding outcomes on inferences about the parameters of a linear regression. Finally, a modest simulation study sheds some light on the finite‐sample behavior of our procedure.     

On the mod sum number of H m,n

Let N denote the set of all positive integers. The sum graph G ⁺(S) of a finite subset S?N is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an mod sum graph if it is isomorphic to the sum graph of some S?Z _M \{0} and all arithmetic performed modulo M where M≥|S|+1. The mod sum number ρ(G) of G is the smallest number of isolated vertices which when added to G result in a mod sum graph. It is known that the graphs H _m,n (n>m≥3) are not mod sum graphs. In this paper we show that H _m,n are not mod sum graphs for m≥3 and n≥3. Additionally, we prove that ρ(H _m,3)=m for m≥3, H _m,n ∪ρK ₁ is exclusive for m≥3 and n≥4 and $m(n-1) \leq \rho(H_{m,n})\leq \frac{1}{2} mn(n-1)$ for m≥3 and n≥4.     

Profile minimization on compositions of graphs

The profile minimization problem arose from the study of sparse matrix technique. In terms of graphs, the problem is to determine the profile of a graph G which is defined as $$P(G)=\min\limits_{f}\sum\limits_{v\in V(G)}\max\limits_{x\in N[v]}(f(v)-f(x)),$$ where f runs over all bijections from V(G) to {1,2,…,|V(G)|} and N[v]={v}∪{x∈V(G):xv∈E(G)}. This is equivalent to the interval graph completion problem, which is to find a super-graph of a graph G with as few number of edges as possible. The purpose of this paper is to study the profiles of compositions of two graphs.     

The broadcast median problem in heterogeneous postal model

We propose the problem of finding broadcast medians in heterogeneous networks. A heterogeneous network is represented by a graph G=(V,E), in which each edge has a weight that denotes the communication time between its two end vertices. The overall delay of a vertex v∈V(G), denoted as b(v,G), is the minimum sum of the communication time required to send a message from v to all vertices in G. The broadcast median problem consists of finding the set of vertices v∈V(G) with minimum overall delay b(v,G) and determining the value of b(v,G). In this paper, we consider the broadcast median problem following the heterogeneous postal model. Assuming that the underlying graph G is a general graph, we show that computing b(v,G) for an arbitrary vertex v∈V(G) is NP-hard. On the other hand, assuming that G is a tree, we propose a linear time algorithm for the broadcast median problem in heterogeneous postal model.     

Approximating the chromatic index of multigraphs

It is well known that if G is a multigraph then χ′(G)≥χ′^*(G):=max {Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′^*(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max {2|E(G[U])|/(|U|−1):U⊆V(G),|U|≥3, |U| is odd}. The conjecture that χ′(G)≤max {Δ(G)+1,⌈Γ(G)⌉} was made independently by Goldberg (Discret. Anal. 23:3–7, 1973), Anderson (Math. Scand. 40:161–175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423–460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′^*(G)+c χ′^*(G) when χ′^*(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋; and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with $\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor , improving the above mentioned results. As a consequence, for multigraphs G with $\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2} the answer to a 1964 problem of Vizing is in the affirmative.     

Circular L(j,k)-labeling number of direct product of path and cycle

Let j, k and m be positive numbers, a circular m-L(j,k)-labeling of a graph G is a function f:V(G)→[0,m) such that |f(u)?f(v)| _m ≥j if u and v are adjacent, and |f(u)?f(v)| _m ≥k if u and v are at distance two, where |a?b| _m =min{|a?b|,m?|a?b|}. The minimum m such that there exist a circular m-L(j,k)-labeling of G is called the circular L(j,k)-labeling number of G and is denoted by σ _j,k (G). In this paper, for any two positive numbers j and k with j≤k, we give some results about the circular L(j,k)-labeling number of direct product of path and cycle.