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.     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

Super restricted edge connected Cartesian product graphs

An edge-cut F of a connected graph G is called a restricted edge-cut if G−F contains no isolated vertices. The minimum cardinality of all restricted edge-cuts is called the restricted edge-connectivity λ^′(G) of G. A graph G is said to be λ^′-optimal if λ^′(G)=ξ(G), where ξ(G) is the minimum edge-degree of G. A graph is said to be super-λ^′ if every minimum restricted edge-cut isolates an edge. This article gives a sufficient condition for Cartesian product graphs to be super-λ^′. Using this result, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to be super-λ^′.     

Hamiltonian connectivity and globally 3∗-connectivity of dual-cube extensive networks

In 2000, Li et al. introduced dual-cube networks, denoted by DC_n for n?1, using the hypercube family Q_n and showed the vertex symmetry and some fault-tolerant hamiltonian properties of DC_n. In this article, we introduce a new family of interconnection networks called dual-cube extensive networks, denoted by DCEN(G). Given any arbitrary graph G, DCEN(G) is generated from G using the similar structure of DC_n. We show that if G is a nonbipartite and hamiltonian connected graph, then DCEN(G) is hamiltonian connected. In addition, if G has the property that for any two distinct vertices u,v of G, there exist three disjoint paths between u and v such that these three paths span the graph G, then DCEN(G) preserves the same property. Furthermore, we prove that the similar results hold when G is a bipartite graph.     

Super connectivity of line graphs

The super connectivity κ^′ and the super edge-connectivity λ^′ are more refined network reliability indices than connectivity κ and edge-connectivity λ. This paper shows that for a connected graph G with order at least four rather than a star and its line graph L(G), κ^′(L(G))=λ^′(G) if and only if G is not super-λ^′. As a consequence, we obtain the result of Hellwig et al. [Note on the connectivity of line graphs, Inform. Process. Lett. 91 (2004) 7] that κ(L(G))=λ^′(G). Furthermore, the authors show that the line graph of a super-λ^′ graph is super-λ if the minimum degree is at least three.     

Relationship between the eccentric connectivity index and Zagreb indices

For a (molecular) graph, the first Zagreb index M₁ is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M₂ is equal to the sum of the products of the degrees of pairs of adjacent vertices. If G is a connected graph with vertex set V(G), then the eccentric connectivity index of G, ξ^C(G), is defined as, ∑_vi∈V(G)d_ie_i, where d_i is the degree of a vertex v_i and e_i is its eccentricity. In this report we compare the eccentric connectivity index (ξ^C) and the Zagreb indices (M₁ and M₂) for chemical trees. Moreover, we compare the eccentric connectivity index (ξ^C) and the first Zagreb index (M₁) for molecular graphs.     

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.     

The oriented chromatic number of Halin graphs

The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H. The oriented chromatic number of an unoriented graph G is the maximal chromatic number over all possible orientations of G. In this paper, we prove that every Halin graph has oriented chromatic number at most 8, improving a previous bound by Hosseini Dolama and Sopena, and confirming the conjecture given by Vignal.     

Model-free Q-learning designs for linear discrete-time zero-sum games with application to H-infinity control

In this paper, the optimal strategies for discrete-time linear system quadratic zero-sum games related to the H-infinity optimal control problem are solved in forward time without knowing the system dynamical matrices. The idea is to solve for an action dependent value function Q(x,u,w) of the zero-sum game instead of solving for the state dependent value function V(x) which satisfies a corresponding game algebraic Riccati equation (GARE). Since the state and actions spaces are continuous, two action networks and one critic network are used that are adaptively tuned in forward time using adaptive critic methods. The result is a Q-learning approximate dynamic programming (ADP) model-free approach that solves the zero-sum game forward in time. It is shown that the critic converges to the game value function and the action networks converge to the Nash equilibrium of the game. Proofs of convergence of the algorithm are shown. It is proven that the algorithm ends up to be a model-free iterative algorithm to solve the GARE of the linear quadratic discrete-time zero-sum game. The effectiveness of this method is shown by performing an H-infinity control autopilot design for an F-16 aircraft.     

Triangulation of molecular surfaces

Given a molecule, which consists of a set of atoms, a molecular surface is defined for a spherical probe approximating a solvent molecule. Molecular surface is used for both the visualization of the molecule and the computation of various molecular properties such as the area and volume of a protein, which are important for studying problems such as protein docking and folding.In this paper, we present an O(n) time algorithm, in the worst case, for triangulating molecular surface based on the combinatorial information provided by the β-shape of the molecule with n atoms. The proposed algorithm takes advantage of the concise representation of topology among atoms stored in the β-shape.A molecular surface consists of two parts: a blending surface consisting of blending patches and a (solvent) contact surface consisting of (solvent) contact patches. For each blending patch, the algorithm uses compact masks for the construction of a triangular mesh in O(c^′) time in the worst case, where c^′ is the number of point evaluations on the blending patch. For each contact patch, the algorithm uses a template, for each atom type, for the triangulation of the boundary of the atom. Then, the triangular mesh is trimmed off by hyperplanes where each hyperplane corresponds to an arc of the boundary of the contact patch. The triangulation of a contact patch takes O(c^″) time in the worst case, where c^″ is the number of point evaluations on the boundary of an atom. Since there are at most O(n) patches, the worst case time complexity is O(n).The proposed algorithm also handles internal voids and guarantees the watertightness of the produced triangular mesh of a molecular surface. In addition, the level-of-detail is easily achieved as a by-product of the proposed scheme. The proposed algorithm is fully implemented and statistics from experiments are also collected.     

Shortest hop multipath algorithm for wireless sensor networks

Shortest hop or distance path is one of the most common methods used for relaying messages in a wide variety of networks. It provides an efficient message relaying to destination in terms of energy and time. There are many algorithms for constructing shortest hop or distance path. However, according to our knowledge, no algorithm for constructing a shortest hop multipath for wireless sensor networks (WSNs) has yet been proposed in the literature. In this paper, we propose a novel distributed shortest hop multipath algorithm for WSNs in order to generate energy efficient paths for data dissemination or routing. The proposed algorithm generates shortest hop braided multipath to be used for fault-tolerance or load-balancing. It guarantees the BFS tree and generates near optimal paths in O(V.D+V) message complexity and O(D²) time complexity regarding the communication costs towards the sink after termination of algorithm.     

Some new sequence spaces derived by the domain of the triple band matrix

Let λ denote any of the classical spaces ?_∞,c,c₀, and ?_p of bounded, convergent, null, and absolutely p-summable sequences, respectively, and let λ(B) also be the domain of the triple band matrix B(r,s,t) in the sequence space λ, where 1<p<∞. The present paper is devoted to studying the sequence space λ(B). Furthermore, the β- and γ-duals of the space λ(B) are determined, the Schauder bases for the spaces c(B), c₀(B), and ?_p(B) are given, and some topological properties of the spaces c₀(B), ?₁(B), and ?_p(B) are examined. Finally, the classes (λ₁(B):λ₂) and (λ₁(B):λ₂(B)) of infinite matrices are characterized, where λ₁∈{?_∞,c,c₀,?_p,?₁} and λ₂∈{?_∞,c,c₀,?₁}.     

Equitable and equitable list colorings of graphs

A proper k-vertex coloring of a graph is an equitable k-coloring if the sizes of the color classes differ by at most 1. A graph G is equitably k-choosable if, for any k-uniform list assignment L, G is L-colorable and each color appears on at most vertices. We prove in this paper that outerplane graphs are equitably k-choosable whenever k≥Δ, where Δ is the maximum degree. Moreover, we discuss equitable colorings of some d-degenerate graphs.     

Improved deterministic algorithms for weighted matching and packing problems

Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O^∗(4^{(r−1)k+o(k)}), improving the previous best upper bound O^∗(4^rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O^∗(16^k+o(k)), improving the previous best result O^∗(21.26^k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O^∗(2^{(2r−1)k+o(k)}), improving the previous best result O^∗(2^2rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O^∗(32^k+o(k)), improving the previous best result O^∗(43.62^k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(k^r), which is the first kernelization algorithm for the problems on weighted versions.     

Three results on frequency assignment in linear cellular networks

In the frequency assignment problem we are given a graph representing a wireless network and a sequence of requests, where each request is associated with a vertex. Each request has two more attributes: its arrival and departure times, and it is considered active from the time of arrival to the time of departure. We want to assign frequencies to all requests so that at each time step any two active requests associated with the same or adjacent vertices use different frequencies. The objective is to minimize the number of frequencies used.We focus exclusively on the special case of the problem when the underlying graph is a linear network (path). For this case, we consider both the offline and online versions of the problem, and we present three results. First, in the incremental online case, where the requests arrive over time, but never depart, we give an algorithm with an optimal (asymptotic) competitive ratio . Second, in the general online case, where the requests arrive and depart over time, we improve the current lower bound on the (asymptotic) competitive ratio to . Third, we prove that the offline version of this problem is NP-complete.     

Online computation with advice

We consider a model for online computation in which the online algorithm receives, together with each request, some information regarding the future, referred to as advice. The advice is a function, defined by the online algorithm, of the whole request sequence. The advice provided to the online algorithm may allow an improvement in its performance, compared to the classical model of complete lack of information regarding the future. We are interested in the impact of such advice on the competitive ratio, and in particular, in the relation between the size b of the advice, measured in terms of bits of information per request, and the (improved) competitive ratio. Since b=0 corresponds to the classical online model, and b=⌈log∣A∣⌉, where A is the algorithm’s action space, corresponds to the optimal (offline) one, our model spans a spectrum of settings ranging from classical online algorithms to offline ones.In this paper we propose the above model and illustrate its applicability by considering two of the most extensively studied online problems, namely, metrical task systems (MTS) and the k-server problem. For MTS we establish tight (up to constant factors) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms with advice for any choice of 1≤b≤Θ(logn), where n is the number of states in the system: we prove that any randomized online algorithm for MTS has competitive ratio Ω(log(n)/b) and we present a deterministic online algorithm for MTS with competitive ratio O(log(n)/b). For the k-server problem we construct a deterministic online algorithm for general metric spaces with competitive ratio k^O(1/b) for any choice of Θ(1)≤b≤logk.