A total-weighting of a graph $G=(V,E)$ is a mapping $f$ which assigns to each element $y\in V\cup E$ a real number $f(y)$ as the weight of $y$. A total-weighting $f$ of $G$ is proper if the coloring $\phi_{f}$ of the vertices of $G$ defined as $\phi_{f}(v)=f(v)+\sum_{e\in E(v)}f(e)$ is a proper coloring of $G$, i.e., $\phi_{f}(v)\ne\phi_{f}(u)$ for any edge $uv$, where $E(v)$ is the set of edges of $G$ incident to $v$. For positive integers $k$ and $k'$, a graph $G$ is called $(k,k')$-total-weight-choosable if whenever each vertex $v$ is given $k$ permissible weights and each edge $e$ is given $k'$ permissible weights, there is a proper total-weighting $f$ of $G$ which uses only permissible weights on each element $y\in V\cup E$. It is known that every tree is (2,2)-total-weight-choosable and every tree other than $K_2$ is (1,3)-total-weight-choosable. However, the problem of determining which trees are (1,2)-total-weight-choosable remained open. This paper solves this problem and characterizes all (1,2)-total-weight-choosable trees. Based on this characterization, we give an algorithm that determines in linear time whether a given tree is (1,2)-total-weight-choosable.

A Roman dominating function of a graph G is a function f$: V(G) \to \{0, 1, 2\}$ such that whenever $f(v)=0$, there exists a vertex u adjacent to v such that $f(u) = 2$. The weight of f is $w(f) = \sum_{v \in V(G)} f(v)$. The Roman domination number $\gamma_R(G)$ of G is the minimum weight of a Roman dominating function of G. Chambers, Kinnersley, Prince, and West [SIAM J. Discrete Math., 23 (2009), pp. 1575–1586] conjectured that $\gamma_R(G) \le \lceil 2n/3 \rceil$ for any 2-connected graph G of n vertices. This paper gives counterexamples to the conjecture and proves that $\gamma_R(G) \le \max\{\lceil 2n/3 \rceil, 23n/34\}$ for any 2-connected graph G of n vertices. We also characterize 2-connected graphs G for which $\gamma_R(G) = 23n/34$ when $23n/34 > \lceil 2n/3 \rceil$.

Abstract Suppose G is a connected graph and T a spanning tree of G. A vertex v ε V(G) is said to be a degree‐preserving vertex if its degree in T is the same as its degree in G. The degree‐preserving spanning tree problem is to find a spanning tree T of a connected graph G such that the number of degree‐preserving vertices is maximized. The purpose of this article is to provide an O(m.α(m,n))‐time algorithm for the degree‐preserving spanning tree problem in strongly chordal graphs, where α is the inverse of Ackermann's function. Furthermore, we present an O(m + n)‐time algorithm in directed path graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

The hierarchical hypercube network is suitable for massively parallel systems. An appealing property of this network is the low number of connections per processor which can facilitate the VLSI design and fabrication of the system. Other alluring features include symmetry and logarithmic diameter, which imply easy and fast algorithms for communication. In this paper, a maximal number of node-disjoint paths are constructed between every two distinct nodes of the hierarchical hypercube network. Their maximal length is not greater than max{2/sup m+1/ + 2m + 1, 2/sup m+1/ + m + 4},where 2/sup m+1/ is the diameter.

(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t /spl ges/k This paper proposes a (t,k) diagnosis algorithm for matching composition networks, which include many well-known interconnection networks such as hypercubes, crossed cubes, twisted cubes, and Mobius cubes. It is shown that matching composition networks of n dimensions are (/spl Omega/(2/sup n//spl middot/logn/n),n)-diagnosable, where n > 5.

In this paper, we study diagnosabilities of multiprocessor systems under two diagnosis models: the PMC model and the comparison model. In each model, we further consider two different diagnosis strategies: the precise diagnosis strategy proposed by Preparata et al. and the pessimistic diagnosis strategy proposed by Friedman. The main result of this paper is to determine diagnosabilities of regular networks with certain conditions, which include several widely used multiprocessor systems such as variants of hypercubes and many others.

Given a nonnegative integer r, a no-hole (r+1)-distant coloring, called $\hbox{N}_{r}$-coloring, of a graph G is a function that assigns a nonnegative integer (color) to each vertex such that the separation of the colors of any pair of adjacent vertices is greater than r,, and the set of the colors used must be consecutive. Given r and G, the minimum N r -span of G, nsp r (G), is the minimum difference of the largest and the smallest colors used in an N r -coloring of G if there exists one; otherwise, define ${\rm nsp}_r(G)=\infty$. The values of nsp 1 (G) (r=1) for bipartite graphs are given by Roberts [Math. Comput. Modelling, 17 (1993), pp. 139--144]. Given $r \geq 2$, we determine the values of nsp r (G) for all bipartite graph with at least r-2 isolated vertices. This leads to complete solutions of nsp 2 (G) for bipartite graphs.

In recent years, many multistage interconnection networks using 2 × 2 switching elements have been proposed for parallel architectures. Typical examples are baseline networks, banyan networks, shuffle-exchange networks, and their inverses. As these networks are blocking, such networks with extra stages have also been studied extensively. These include Benes networks and Δ ⊕ Δ′ networks. Recently, Hwang et al. studied k-extra-stage networks, which are a generalization of the above networks. They also investigated the equivalence issue among some of these networks. In this paper, we studied a more general class of networks, which we call (m + 1)-stage d-nary bit permutation networks. We characterize the equivalence of such networks by sequence of positive integers. © 1999 John Wiley & Sons, Inc. Networks 33: 261–267, 1999

Suppose G=(V,E) is a simple graph and k is a fixed positive integer. A vertex zk-neighborhood-covers an edge (x,y) if d(z,x) \leq k$ and d(z,y) \leq k$. A k-neighborhood-covering set is a set C of vertices such that every edge in E is k-neighborhood-covered by some vertex in C. A k-neighborhood-independent set is a set of edges in which no two distinct edges can be k-neighborhood-covered by the same vertex in V. In this paper we first prove that the k-neighborhood-covering and the k-neighborhood-independence problems are NP-complete for chordal graphs. We then present a linear-time algorithm for finding a minimum k-neighborhood-covering set and a maximum k-neighborhood-independent set for a strongly chordal graph provided that a strong elimination ordering is given in advance.

We consider the problem of partitioning the vertex-set of a tree to p parts to minimize a cost function. Since the number of partitions is exponential in the number of vertices, it is helpful to identify small classes of partitions which also contain optimal partitions. Two such classes, called consecutive partitions and nested partitions, have been well studied for the set partition problem, which is a special case of the tree-partition problem when the tree is a path. We give conditions on the optimality of these classes on tree partitions and also extend our results to tree networks. © 1997 John Wiley & Sons, Inc. Networks 30: 75–80, 1997

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) | \geq 2$ if $d(x,y) = 1$ and $| f(x) - f(y) | \geq 1$ if $d(x,y) = 2$. The $L(2,1)$-labeling number $\lambda (G)$ of G is the smallest number k such that G has an $L(2,1)$-labeling with $\max\{ f(v ):v \in V(G) \} = k$. In this paper, we give exact formulas of $\lambda (G \cup H)$ and $\lambda (G + H)$. We also prove that $\lambda (G) \leq \Delta ^2 + \Delta $ for any graph G of maximum degree $\Delta $. For odd-sun-free (OSF)-chordal graphs, the upper bound can be reduced to $\lambda (G) \leq 2\Delta + 1$. For sun-free (SF)-chordal graphs, the upper bound can be reduced to $\lambda (G) \leq \Delta + 2\chi (G) - 2$. Finally, we present a polynomial time algorithm to determine $\lambda (T)$ for a tree T.

The profile minimization problem is to find a one-to-one function f from the vertex set $V(G)$ of a graph G to the set of all positive integers such that $\sum _{x \in V(G)} \{ f(x) - \min _{y \in N[x]} f(y)\} $ is as small as possible, where $N[x] = \{ x\} \cup \{ y:y{\text{ is adjacent }}x \} $ is the closed neighborhood of x in G. This paper gives an $O(n^{1.722} )$ time algorithm for the problem in a tree of n vertices.

In a graph $G = ( V,E ),E [ v ]$ denotes the set of edges in the subgraph induced by $N [ v ] \equiv \{ v \} \cup \{ u \in V:uv \in E \}$. The neighborhood-covering problem is to find the minimum cardinality of a set C of vertices such that $E = \cup \{ E [ v ]:v \in C \}$. The neighborhood-independence problem is to find the maximum cardinality of a set of edges in which there are no two distinct edges belonging to the same $E [ v ]$ for any $v \in V$. Two other related problems are the clique-transversal problem and the clique-independence problem. It is shown that these four problems are NP-complete in split graphs with degree constraints and linear time algorithms for them are given in a strongly chordal graph when a strong elimination order is given.

A set of vertices D is a dominating set of a graph $G = ( V,E )$ if every vertex in $V - D$ is adjacent to a vertex in D. The domatic number $d ( G )$ of a graph $G = ( V,E )$ is the maximum number k such that V can be partitioned into k disjoint dominating sets $D_1 , \cdots ,D_k $. The main purpose of this paper is to give linear algorithms for the domatic number problem in interval graphs. This paper also proves that $d ( G ) = \delta ( G ) + 1$ for any interval graph G, where $\delta ( G )$ is the minimum degree of a vertex in G.