Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

Dynamic Waveband Switching in WDM Mesh Networks Based on a Generic Auxiliary Graph Model

Waveband switching (WBS) is a promising technique to reduce the switching and transmission costs in the optical domain of a wavelength-division multiplexing (WDM) network. This paper considers the problem of provisioning dynamic traffic using WBS in a WDM mesh network. The network of interest is a homogeneous WBS network, where each node has the functionality of WBS. The problem is called the dynamic WBS problem, which involves searching waveband-routes or wavelength-routes for the dynamically arriving traffic requests. The objective is to minimize the total switching and transmission costs in the optical domain. To solve the dynamic WBS problem, an auxiliary graph model capturing the network state is proposed. Based on the auxiliary graph, two heuristic on-line WBS algorithms with different waveband grouping policies are proposed, namely the wavelength-first WBS algorithm based on the auxiliary graph (WFAUG) and the waveband-first WBS algorithm based on the auxiliary graph (BFAUG). Simulation results indicate that WBS is an attractive technique which reduces the overall switching and transmission costs by up to 30% in the network. The results also show that the WFAUG algorithm outperforms the BFAUG algorithm in terms of port savings and cost savings.     

Structural and magnetic properties of RF sputtered FePt/Fe multilayers

Series of [FePt(4min)/Fe(t_Fe)]₁₀ multilayers have been prepared by RF magnetron sputtering and post-annealing in order to optimize their magnetic properties by structural designs. The structure, surface morphology, composition and magnetic properties of the deposited films have been characterized by X-ray diffractometer (XRD), Rutherford backscattering (RBS), scanning electron microscope (SEM), energy dispersive X-ray spectroscope (EDX) and vibrating sample magnetometer (VSM). It is found that after annealing at temperatures above 500 °C, FePt phase undergoes a phase transition from disordered FCC to ordered FCT structure, and becomes a hard magnetic phase. X-ray diffraction studies on the series of [FePt/Fe]_n multilayer with varying Fe layer thickness annealed at 500 and 600 °C show that lattice constants change with Fe layer thickness and annealing temperature. Both lattice constants a and c are smaller than those of standard ones, and lattice constant a decreases as Fe layer deposition time increases. Only a slight increase in grain size was observed as Fe layer decreased in samples annealed at 500 °C. However, the increase in grain size is large in samples annealed at 600 °C. The coercivities of [FePt/Fe]_n multilayers decrease with Fe layer deposition time, and the energy product (BH)_max reaches a maximum in the samples with Fe layer deposition time of 3 min. Comparison of magnetic properties with structure showed an almost linear relationship between the lattice constant a and the coercivities of the FePt phase.     

On potentially <Emphasis Type="Italic">H</Emphasis>-graphic sequences

For given a graph H, a graphic sequence π = (d ₁, d ₂,..., d _n) is said to be potentially H-graphic if there is a realization of π containing H as a subgraph. In this paper, we characterize the potentially (K ₅ − e)-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence π to be potentially K ₅-graphic, where K _r is a complete graph on r vertices and K _r-e is a graph obtained from K _r by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence π to be potentially K ₆-graphic. Project supported by National Natural Science Foundation of China (No. 10401010).     

Drawing c-planar biconnected clustered graphs

In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph C consists of a graph G and a set of non-intersecting clusters. In this paper, we assume that C has a compound planar drawing and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight-line segments with no edge crossing and (ii) the boundary of the biconnected subgraph induced by each cluster is a convex polygon.     

Partitioning series-parallel multigraphs into ν *-excluding edge covers

We prove that, for any given vertex ν* in a series-parallel graph G, its edge set can be partitioned into κ = min{κ′(G) + 1, δ(G)} subsets such that each subset covers all the vertices of G possibly except for ν*, where δ(G) is the minimum degree of G and κ′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.     

Sizes of Critical Graphs with Small Maximum Degrees

In this paper, we give new lower bounds for the size of Δ-critical graphs with Δ=8,9 which improve the partial results of Luo [6] and Y. Zhao [12].     

High temperature annealing effect on structural and magnetic properties of Ti/Ni multilayers

High temperature annealing effect on structural and magnetic properties of Ti/Ni multilayer (ML) up to 600 °C have been studied and reported in this paper. Ti/Ni multilayer samples having constant layer thicknesses of 50 Å each are deposited on float glass and Si(1 1 1) substrates using electron-beam evaporation technique under ultra-high vacuum (UHV) conditions at room temperatures. The micro-structural parameters and their evolution with temperature for as-deposited as well as annealed multilayer samples up to 600 °C in a step of 100 °C for 1 h are determined by using X-ray diffraction (XRD) and grazing incidence X-ray reflectivity techniques. The X-ray diffraction pattern recorded at 300 °C annealed multilayer sample shows interesting structural transformation (from crystalline to amorphous) because of the solid-state reaction (SSR) and subsequent re-crystallization at higher temperatures of annealing, particularly at ≥400 °C due to the formation of TiNi₃ and Ti₂Ni alloy phases. Sample quality and surface morphology are examined by using atomic force microscopy (AFM) technique for both as-deposited as well as annealed multilayer samples. In addition to this, a temperature dependent dc resistivity measurement is also used to study the structural transformation and subsequent alloy phase formation due to annealing treatment. The corresponding magnetization behavior of multilayer samples after each stage of annealing has been investigated by using Magneto-Optical Kerr Effect (MOKE) technique and results are interpreted in terms of observed micro-structural changes.     

Enumeration of perfect matchings of a type of Cartesian products of graphs

Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by P_m and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let C_n denote the cycle with n vertices. Then Pm(C₄×T)=∏(2+α²), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C₄×T) is always a square or double a square.2. Let T be a tree. Then Pm(P₄×T)=∏(1+3α²+α⁴), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P₃×T)=∏(2+α²), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C₄×T)=[Pm(P₃×T)]².