The edge-orientation problem and some of its variants on weighted graphs

Let G(V, E) be a connected undirected graph with n vertices and m edges, where each vertex v is associated with a cost C(v) and each edge e = (u, v) is associated with two weights, W(u → v) and W(v → u). The issue of assigning an orientation to each edge so that G becomes a directed graph is resolved in this paper. Determining a scheme to assign orientations of all edges such that max_x∈V{C(x)+∑_x→zW(x→z)} is minimized is the objective. This issue is called the edge-orientation problem (the EOP). Two variants of the EOP, the Out-Degree-EOP and the Vertex-Weighted EOP, are first proposed and then efficient algorithms for solving them on general graphs are designed. Ascertaining that the EOP is NP-hard on bipartite graphs and chordal graphs is the second result. Finally, an O(n log n)-time algorithm for the EOP on trees is designed. In general, the algorithmic results in this paper facilitate the implementation of the weighted fair queuing (WFQ) on real networks. The objective of the WFQ is to assign an effective weight for each flow to enhance link utilization. Our findings consequently can be easily extended to other classes of graphs, such as cactus graphs, block graphs, and interval graphs.     

Upper signed k-domination in a general graph

Let k be a positive integer, and let G=(V,E) be a graph with minimum degree at least k−1. A function f:V→{−1,1} is said to be a signed k-dominating function (SkDF) if _∑u∈N[v]f(u)?k for every v∈V. An SkDF f of a graph G is minimal if there exists no SkDF g such that g≠f and g(v)?f(v) for every v∈V. The maximum of the values of _∑v∈Vf(v), taken over all minimal SkDFs f, is called the upper signed k-domination numberΓkS(G). In this paper, we present a sharp upper bound on this number for a general graph.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

Signed and minus clique-transversal functions on graphs

A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function (respectively, {−1,1}) such that _∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=_∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs.     

Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the edges and the vertices. A total coloring is proper if no two adjacent or incident elements receive the same color. An adjacent vertex-distinguishing total coloring h of a simple graph G=(V,E) is a proper total coloring of G such that H(u)≠H(v) for any two adjacent vertices u and v, where H(u)={h(wu)|wu∈E(G)}∪{h(u)} and H(v)={h(xv)|xv∈E(G)}∪{h(v)}. The minimum number of colors required for an adjacent vertex-distinguishing edge coloring (resp. an adjacent vertex-distinguishing total coloring) of G is called the adjacent vertex-distinguishing edge chromatic number (resp. adjacent vertex-distinguishing total chromatic number) of G and denoted by (resp. χat(G)). In this paper, we consider the adjacent vertex-distinguishing edge chromatic number and adjacent vertex-distinguishing total chromatic number of the hypercube Qn, prove that for n?3 and χat(Qn)=Δ(Qn)+2 for n?2.     

Oriented colorings of partial 2-trees

A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping f from V(G) to V(H), that is f(x)f(y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the minimum order of an oriented graph H such that G has a homomorphism to H. In this paper, we determine the oriented chromatic number of the class of partial 2-trees for every girth g?3. We also give an upper bound for the oriented chromatic number of planar graphs with girth at least 11.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

On the oriented chromatic number of grids

In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph G without symmetric arcs such that (i) no two neighbors in G are assigned the same color, and (ii) if two vertices u and v such that (u,v)∈A(G) are assigned colors c(u) and c(v), then for any (z,t)∈A(G), we cannot have simultaneously c(z)=c(v) and c(t)=c(u). The oriented chromatic number of an unoriented graph G is the smallest number k of colors for which any of the orientations of G can be colored with k colors.The main results we obtain in this paper are bounds on the oriented chromatic number of particular families of planar graphs, namely 2-dimensional grids, fat trees and fat fat trees.     

Consensus models: Computational complexity aspects in modern approaches to the list coloring problem

In the paper we study new approaches to the problem of list coloring of graphs. In the problem we are given a simple graph G=(V,E) and, for every v∈V, a nonempty set of integers S(v); we ask if there is a coloring c of G such that c(v)∈S(v) for every v∈V. Modern approaches, connected with applications, change the question—we now ask if S can be changed, using only some elementary transformations, to ensure that there is such a coloring and, if the answer is yes, what is the minimal number of changes. In the paper for studying the adding, the trading and the exchange models of list coloring, we use the following transformations:

•

adding of colors (the adding model): select two vertices u, v and a color c∈S(u); add c to S(v), i.e. set S(v):=S(v)∪{c};

•

trading of colors (the trading model): select two vertices u, v and a color c∈S(u); move c from S(u) to S(v), i.e. set S(u):=S(u)?{c} and S(v):=S(v)∪{c};

•

exchange of colors (the exchange model): select two vertices u, v and two colors c∈S(u), d∈S(v); exchange c with d, i.e. set S(u):=(S(u)?{c})∪{d} and S(v):=(S(v)?{d})∪{c}.

Our study focuses on computational complexity of the above models and their edge versions. We consider these problems on complete graphs, graphs with bounded cyclicity and partial k-trees, receiving in all cases polynomial algorithms or proofs of NP-hardness.     

Complexity of homomorphisms to direct products of graphs

For a graph G, OALG asks whether or not an input graph H together with a partial map g:S→G, S⊆V(H), admits a homomorphism f:H→G such that f|_S=g. We show that for connected graphs G₁, G₂, OAL G₁×G₂ is in P if G₁ and G₂ are trees and NP-complete otherwise.     

Testing list <Emphasis Type="Italic">H</Emphasis>-homomorphisms

In the List H- Homomorphism Problem, for a graph H that is a parameter of the problem, an instance consists of an undirected graph G with a list constraint \({L(v) \subseteq V(H)}\) for each variable \({v \in V(G)}\), and the objective is to determine whether there is a list H-homomorphism \({f:V(G) \to V(H)}\), that is, \({f(v) \in L(v)}\) for every \({v \in V(G)}\) and \({(f(u),f(v)) \in E(H)}\) whenever \({(u,v) \in E(G)}\).We consider the problem of testing list H-homomorphisms in the following weighted setting: An instance consists of an undirected graph G, list constraints L, weights imposed on the vertices of G, and a map \({f:V(G) \to V(H)}\) given as an oracle access. The objective is to determine whether f is a list H-homomorphism or far from any list H-homomorphism. The farness is measured by the total weight of vertices \({v \in V(G)}\) for which f(v) must be changed so as to make f a list H-homomorphism. In this paper, we classify graphs H with respect to the number of queries to f required to test the list H-homomorphisms. Specifically, we show that (i) list H-homomorphisms are testable with a constant number of queries if and only if H is a reflexive complete graph or an irreflexive complete bipartite graph and (ii) list H-homomorphisms are testable with a sublinear number of queries if and only if H is a bi-arc graph.     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.     

Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):vV(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ² for any simple graph with maximum degree Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.     

On the oriented chromatic number of Halin graphs

An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.     

Oriented vertex and arc colorings of outerplanar graphs

A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping φ from V(G) to V(H), that is φ(x)φ(y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the minimum order of an oriented graph H such that G has a homomorphism to H. The oriented chromatic index of G is the minimum order of an oriented graph H such that the line-digraph of G has a homomorphism to H.In this paper, we determine for every k?3 the oriented chromatic number and the oriented chromatic index of the class of oriented outerplanar graphs with girth at least k.     

A new approach for approximating node deletion problems

We present a new approach for approximating node deletion problems by combining the local ratio and the greedy multicovering algorithms. For a function , our approach allows to design a 2+max_v∈V(G)logf(v) approximation algorithm for the problem of deleting a minimum number of nodes so that the degree of each node v in the remaining graph is at most f(v). This approximation ratio is shown to be asymptotically optimal. The new method is also used to design a 1+(log2)(k−1) approximation algorithm for the problem of deleting a minimum number of nodes so that the remaining graph contains no k-bicliques.     

The algorithmic complexity of mixed domination in graphs

Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset W⊆V∪E is a mixed dominating set if every element x∈(V∪E)?W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.