N-Set Distance-Labelings for Cycle Graphs

Let G = (V, E) be a graph and Cm be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm. An n-set distance labeling of a graph G is the labeling of the vertices (with n labels per vertex) of G under certain constraints depending on the distance between each pair of the vertices in G. Following Yeh’s notation [1], the smallest value for the largest label in an n-set distance labeling of G is denoted by λ1(n)(G). Basic results were presented in [1] for λ1(2)(Cm) for all m and λ1(n)(Cm) for some m where n ≥ 3. However, there were still gaps left unstudied due to case-by-case complexities. For these uncovered cases, we proved a lower bound for λ1(n)(Cm). Then we proposed an algorithm for finding an n-set distance labeling for n ≥ 3 based on our proof of the lower bound. We verified every single case for n = 3 up to n = 500 by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500.

An Alternative Proof of the Largest Number of Maximal Independent Sets in Connected Graphs Having at Most Two Cycles

G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.

Two Results on Uniquely r-Pancyclic Graphs

In this paper,we prove that there does not exist an r-UPC[2]-graph for each r≥5 and there does not exist an r-UPC[C_t^2]-graph for each r≥3,where t is the number of bridges in a graph and C_t^2 is the number of combinations of t bridges taken 2 at a time.

On Simple MCD-Graphs

A simple graph G on n vettices is said to be a simple MCD-graph if G has no two cyties having the same length and has the maximum possible number of edges.Two results of the number of cy cles in G are given by introdueing the Concept of a path decomposition and by them,the following theorem is proved:If G is a simple MCD-graph,then G is not a 2-connected planar graph and for all n except seven integer,G is not a 2-connected graph on n vertices containing a subgraph homeomor phic to K_4.

Edge choosability of planar graphs without short cycles

In this paper we prove that if G is a planar graph with △= 5 and without 4-cycles or 6-cycles, then G is edge-6-choosable. This consequence together with known results show that, for each fixed k ∈{3,4,5,6}, a k-cycle-free planar graph G is edge-(△+ 1)-choosable, where △ denotes the maximum degree of G.

Unimodality of Independence Polynomials of the Cycle Cover Product of Graphs

An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called the independence polynomial of G(Gutman and Harary,1983).In this paper,we introduce a new graph operation called the cycle cover product and formulate its independence polynomial.We also give a criterion for formulating the independence polynomial of a graph.Based on the exact formulas,we prove some results on symmetry,unimodality,reality of zeros of independence polynomials of some graphs.As applications,we give some new constructions for graphs having symmetric and unimodal independence polynomials.

A Note on List Edge and List Total Coloring of Planar Graphs without Adjacent Short Cycles

LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic numberχl（G）=Δ＋1.

Star-Chromatic Numbers of Planar Graphs

The concept of the star chromatic number of a graph was introduced by A.Vince in ,which is a natural generalizition of the chromatic number of a graph.In this paper,we investigate the star chromatic number of a family of planar graphs.More precisely, a family of planar graphs whose star chromatic numbers are between 2 and 3 are disscused,which answers the open problem posed by Vince in .

Test sequencing problem arising at the design stage for reducing life cycle cost

Previous test sequencing algorithms only consider the execution cost of a test at the application stage. Due to the fact that the placement cost of some tests at the design stage is considerably high compared with the execution cost, the sequential diagnosis strategy obtained by previous methods is actually not optimal from the view of life cycle. In this paper, the test sequencing problem based on life cycle cost is presented. It is formulated as an optimization problem, which is non-deterministic polynomial-time hard （NP-hard）. An algorithm and a strategy to improve its computational efficiency are proposed. The formulation and algorithms are tested on various simulated systems and comparisons are made with the extant test sequencing methods. Application on a pump rotational speed control （PRSC） system of a spacecraft is studied in detail. Both the simulation results and the real-world case application results suggest that the solution proposed in this paper can significantly reduce the life cycle cost of a sequential fault diagnosis strategy.