‘Studies on some topics in product graphs’

For routing problems in interconnection networks it is important to find the shortest containers between any two vertices, since the w-wide diameter gives the maximum communication delay when there are up to w−1 faulty nodes in a network modeled by a graph. The concept of ‘wide diameter’ was introduced by Hsu [41] to unify the concepts of diameter and The concept of ‘domination’ has attracted interest due to its wide applications in many real world situations [38]. A connected dominating set serves as a virtual backbone of a network and it is a set of vertices that helps in routing. In this thesis, we make an earnest attempt to study some of these notions in graph products. This include, the diameter variability, the diameter vulnerability, the component factors and the domination criticality.connectivity

Fair Sets of Some Classes of Graphs

Given a non empty set S of vertices of a graph, the partiality of a vertex with respect to S is the di erence between maximum and minimum of the distances of the vertex to the vertices of S. The vertices with minimum partiality constitute the fair center of the set. Any vertex set which is the fair center of some set of vertices is called a fair set. In this paper we prove that the induced subgraph of any fair set is connected in the case of trees and characterise block graphs as the class of chordal graphs for which the induced subgraph of all fair sets are connected. The fair sets of Kn, Km;n, Kn e, wheel graphs, odd cycles and symmetric even graphs are identi ed. The fair sets of the Cartesian product graphs are also discussed

The Wiener, Eccentric Connectivity and Zagreb Indices of the Hierarchical Product of Graphs

Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs having a distinguished or root vertex, labeled 0. The hierarchical product G2 ⊓ G1 of G2 and G1 is a graph with vertex set V2 × V1. Two vertices y2y1 and x2x1 are adjacent if and only if y1x1 ∈ E1 and y2 = x2; or y2x2 ∈ E2 and y1 = x1 = 0. In this paper, the Wiener, eccentric connectivity and Zagreb indices of this new operation of graphs are computed. As an application, these topological indices for a class of alkanes are computed. ACM Computing Classification System (1998): G.2.2, G.2.3.

On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

Factorizations of and by powers of complete graphs

Let K-k(d) denote the Cartesian product of d copies of the complete graph K-k. We prove necessary and sufficient conditions for the existence of a K-k(r)-factorization of K-pn(s), where p is prime and k > 1, n, r and s are positive integers. (C) 2002 Elsevier Science B.V. All rights reserved.

Minimization of open orders using interval graphs

In this paper we address an order processing optimization problem known as the Minimization of Open Stacks Problem (MOSP). This problem consists in finding the best sequence for manufacturing the different products required by costumers, in a setting where only one product can be made at a time. The objective is to minimize the maximum number of incomplete orders from costumers that are being processed simultaneously. We present an integer programming model, based on the existence of a perfect elimination order in interval graphs, which finds an optimal sequence for the costumers orders. Among other economic advantages, manufacturing the products in this optimal sequence reduces the amount of space needed to store incomplete orders.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Antimedian graphs

Antimedian graphs are introduced as the graphs in which for every triple of vertices there exists a unique vertex x that maximizes the sum of the distances from x to the vertices of the triple. The Cartesian product of graphs is antimedian if and only if its factors are antimedian. It is proved that multiplying a non-antimedian vertex in an antimedian graph yields a larger antimedian graph. Thin even belts are introduced and proved to be antimedian. A characterization of antimedian trees is given that leads to a linear recognition algorithm.

Strongly distance-balanced graphs and graph products

A graph G is strongly distance-balanced if for every edge uv of G and every i 0 the number of vertices x with d.x; u/ D d.x; v/ 1 D i equals the number of vertices y with d.y; v/ D d.y; u/ 1 D i. It is proved that the strong product of graphs is strongly distance-balanced if and only if both factors are strongly distance-balanced. It is also proved that connected components of the direct product of two bipartite graphs are strongly distancebalanced if and only if both factors are strongly distance-balanced. Additionally, a new characterization of distance-balanced graphs and an algorithm of time complexity O.mn/ for their recognition, wheremis the number of edges and n the number of vertices of the graph in question, are given

Indirect polarographic and cathodic stripping voltammetric determination of cefaclor as an alkaline degradation product

Cefaclor is not reducible at a mercury electrode, but it can be determined polarographically and by cathodic stripping voltammetry as its initial alkaline degradation product which is obtained in high yield by hydrolysis of cefaclor in Britton-Robinson (B-R) buffer pH 10 at 50 degrees C for 30 min (reduction peak at pH 10, -0.70 V). Differential pulse polarographic calibration graphs are linear up to at least 1 x 10(-4) mol l(-1). Recoveries of 93% of the cefaclor (n = 3) were obtained from urine spiked with 38.6 mu g ml(-1) using this polarographic method with 1 ml urine made up to 10 ml with pH 10 buffer. Using cathodic stripping voltammetry and accumulating at a hanging mercury drop electrode at -0.2 V for 30 s, linear calibration graphs were obtained from 0.35 to 40 mu g ml(-1) cefaclor in B-R buffer pH 10. A relative standard deviation of 4.2% (eta = 5) was obtained, and the limit of detection was calculated to be 2.9 ng ml(-1). Direct determination of cefaclor in human urine (1 ml of urine was made up to 10 ml with pH 10 buffer) spiked to 0.39 mu g ml(-1) was made (recovery 98.6%). (C) 1999 Elsevier B.V. B.V. All rights reserved.

Advanced Characterisation of a Coffee Fermenting Tank by Multi-distributed Wireless Sensors: Spatial Interpolation and Phase Space Graphs

The fermentation stage is considered to be one of the critical steps in coffee processing due to its impact on the final quality of the product. The objective of this work is to characterise the temperature gradients in a fermentation tank by multi-distributed, low-cost and autonomous wireless sensors (23 semi-passive TurboTag® radio-frequency identifier (RFID) temperature loggers). Spatial interpolation in polar coordinates and an innovative methodology based on phase space diagrams are used. A real coffee fermentation process was supervised in the Cauca region (Colombia) with sensors submerged directly in the fermenting mass, leading to a 4.6 °C temperature range within the fermentation process. Spatial interpolation shows a maximum instant radial temperature gradient of 0.1 °C/cm from the centre to the perimeter of the tank and a vertical temperature gradient of 0.25 °C/cm for sensors with equal polar coordinates. The combination of spatial interpolation and phase space graphs consistently enables the identification of five local behaviours during fermentation (hot and cold spots).

Application of central composite rotatable design to modelling the effect of some operating variables on the performance of the three-product cyclone

The central composite rotatable design (CCRD) was used to design an experimental program to model the effects of inlet pressure, feed density, and length and diameter of the inner vortex finder on the operational performance of a 150-min three-product cyclone. The ranges of values of the variables used in the design were: inlet pressure: 80-130 kPa, feed density: 30 60%; length of IVF below the OVF: 50-585 mm; diameter of IVF: 35-50 mm. A total of 30 tests were conducted, which is 51 less; an that required for a three-level full factorial design. Because the model allows confident performance prediction by interpolation over the range of data in the database, it was used to construct response surface graphs to describe the effects of the variables on the performance of the three-product cyclone. To obtain a simple and yet a realistic model, it was refitted using only the variable terms that are significant at greater than or equal to 90% confidence level. Considering the selected operating variables, the resultant model is significant and predicts the experimental data well. (c) 2005 Elsevier B.V. All rights reserved.

Non -traded goods, product differentiation and integration of factor markets

This research sought to determine the implications of a non-traded differentiated commodity produced with increasing returns to scale, for the welfare of countries that allowed free international migration. We developed two- and three-country Ricardian models in which labor was the only factor of production. The countries traded freely in homogeneous goods produced with constant returns to scale. Each also had a non-traded differentiated good sector where production took place using increasing returns to scale technology. Then we allowed for free international migration between two of the countries and observed what happened to welfare in both countries as indicated by their per capita utilities in the new equilibrium relative to their pre-migration utilities. ^ Preferences of consumers were represented by a two-tier utility function [Dixit and Stiglitz 1977]. As migration took place it impacted utility in two ways. The expanding country enjoyed the positive effect of increased product diversity in the non-traded good sector. However, it also suffered adverse terms-of-trade as its production cost declined. The converse was true for the contracting country. To determine the net impact on welfare we derived indirect per capita utility functions of the countries algebraically and graphically. Then we juxtaposed the graphs of the utility functions to obtain possible general equilibria. These we used to observe the welfare outcomes. ^ We found that the most likely outcomes were either that both countries gained, or one country lost while the other gained. We were, however, able to generate cases where both countries lost as a result of allowing free inter-country migration. This was most likely to happen when the shares of income spent on each country's export good differed significantly. In the three country world when we allowed two of the countries to engage in preferential trading arrangements while imposing a prohibitive tariff on imports from the third country welfare of the partner countries declined. When inter-union migration was permitted welfare declined even further. This we showed was due to the presence of the non-traded good sector. ^

Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs

Consider two graphs G and H. Let H^k[G] be the lexicographic product of H^k and G, where H^k is the lexicographic product of the graph H by itself k times. In this paper, we determine the spectrum of H^k[G]H and H^k when G and H are regular and the Laplacian spectrum of H^k[G] and H^k for G and H arbitrary. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10^100 ) of vertices is determined. The paper finishes with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers.

Random walk with restart over dynamic graphs

Random Walk with Restart (RWR) is an appealing measure of proximity between nodes based on graph structures. Since real graphs are often large and subject to minor changes, it is prohibitively expensive to recompute proximities from scratch. Previous methods use LU decomposition and degree reordering heuristics, entailing O(|V|^3) time and O(|V|^2) memory to compute all (|V|^2) pairs of node proximities in a static graph. In this paper, a dynamic scheme to assess RWR proximities is proposed: (1) For unit update, we characterize the changes to all-pairs proximities as the outer product of two vectors. We notice that the multiplication of an RWR matrix and its transition matrix, unlike traditional matrix multiplications, is commutative. This can greatly reduce the computation of all-pairs proximities from O(|V|^3) to O(|delta|) time for each update without loss of accuracy, where |delta| (<<|V|^2) is the number of affected proximities. (2) To avoid O(|V|^2) memory for all pairs of outputs, we also devise efficient partitioning techniques for our dynamic model, which can compute all pairs of proximities segment-wisely within O(l|V|) memory and O(|V|/l) I/O costs, where 1<=l<=|V| is a user-controlled trade-off between memory and I/O costs. (3) For bulk updates, we also devise aggregation and hashing methods, which can discard many unnecessary updates further and handle chunks of unit updates simultaneously. Our experimental results on various datasets demonstrate that our methods can be 1–2 orders of magnitude faster than other competitors while securing scalability and exactness.