Studies of Graph-Structural Properties on Fault-Tolerance of Networks and Design of Improved Algorithms.

点击翻译按钮获取中文摘要

(1) We show that there are two completely independent spanning trees in the Cartesian product of 2-connected graphs. Also, we determine the(h, k)-domination number of an iterated line digraph.(2) We improve upper and lower bounds on the minimum size of a fault-tolerant gossip graph.(3) We design a linear time algorithm for computing the L(2, 1)-labeling number of a tree. Besides, we present tight upper and lower bounds on the(p, q)-total labeling number of a tree and a tight upper bound on the(2, 1)-total labeling number of an outerplanar graph.(4) We design a linear time algorithm for computing the queue-number of a maximal outerplanar graph.