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

On The Center Sets and Center Numbers of Some Graph Classes

For a set S of vertices and the vertex v in a connected graph G, max x2S d(x, v) is called the S-eccentricity of v in G. The set of vertices with minimum S-eccentricity is called the S-center of G. Any set A of vertices of G such that A is an S-center for some set S of vertices of G is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, Km,n, Kn −e, wheel graphs, odd cycles and symmetric even graphs and enumerate them for many of these graph classes. We also introduce the concept of center number which is defined as the number of distinct center sets of a graph and determine the center number of some graph classes

Fixed block configuration GDDs with block size 6 and (3, r)-regular graphs

Chapter 1 is used to introduce the basic tools and mechanics used within this thesis. Most of the definitions used in the thesis will be defined, and we provide a basic survey of topics in graph theory and design theory pertinent to the topics studied in this thesis. In Chapter 2, we are concerned with the study of fixed block configuration group divisible designs, GDD(n; m; k; λ1; λ2). We study those GDDs in which each block has configuration (s; t), that is, GDDs in which each block has exactly s points from one of the two groups and t points from the other. Chapter 2 begins with an overview of previous results and constructions for small group size and block sizes 3, 4 and 5. Chapter 2 is largely devoted to presenting constructions and results about GDDs with two groups and block size 6. We show the necessary conditions are sufficient for the existence of GDD(n, 2, 6; λ1, λ2) with fixed block configuration (3; 3). For configuration (1; 5), we give minimal or nearminimal index constructions for all group sizes n ≥ 5 except n = 10, 15, 160, or 190. For configuration (2, 4), we provide constructions for several families ofGDD(n, 2, 6; λ1, λ2)s. Chapter 3 addresses characterizing (3, r)-regular graphs. We begin with providing previous results on the well studied class of (2, r)-regular graphs and some results on the structure of large (t; r)-regular graphs. In Chapter 3, we completely characterize all (3, 1)-regular and (3, 2)-regular graphs, as well has sharpen existing bounds on the order of large (3, r)- regular graphs of a certain form for r ≥ 3. Finally, the appendix gives computational data resulting from Sage and C programs used to generate (3, 3)-regular graphs on less than 10 vertices.

Signal-flow graphs: Direct method of reduction and MATLAB implementation

Block diagrams and signal-flow graphs are used to represent and to obtain the transfer function of interconnected systems. The reduction of signal-flow graphs is considered simpler than the reduction of block diagrams for systems with complex interrelationships. Signal-flow graphs reduction can be made without graphic manipulations of diagrams, and it is attractive for a computational implementation. In this paper the authors propose a computational method for direct reduction of signal-flow graphs. This method uses results presented in this paper about the calculation of literal determinants without symbolic mathematics tools. The Cramer's rule is applied for the solution of a set of linear equations, A program in MATLAB language for reduction of signal-flow graphs with the proposed method is presented.

Variance dispersion graphs for comparing blocked response surface designs

In this paper, we extend the use of the variance dispersion graph (VDG) to experiments in which the response surface (RS) design must be blocked. Through several examples we evaluate the prediction performances of RS designs in non-orthogonal block designs compared with the equivalent unblocked designs and orthogonally blocked designs. These examples illustrate that good prediction performance of designs in small blocks can be expected in practice. Most importantly, we show that the allocation of the treatment set to blocks can seriously affect the prediction properties of designs; thus, much care is needed in performing this allocation.

Horizontal visibility graphs generated by type-I intermittency

The type-I intermittency route to (or out of) chaos is investigated within the horizontal visibility (HV) graph theory. For that purpose, we address the trajectories generated by unimodal maps close to an inverse tangent bifurcation and construct their associatedHVgraphs.We showhowthe alternation of laminar episodes and chaotic bursts imprints a fingerprint in the resulting graph structure. Accordingly, we derive a phenomenological theory that predicts quantitative values for several network parameters. In particular, we predict that the characteristic power-law scaling of the mean length of laminar trend sizes is fully inherited by the variance of the graph degree distribution, in good agreement with the numerics. We also report numerical evidence on how the characteristic power-law scaling of the Lyapunov exponent as a function of the distance to the tangent bifurcation is inherited in the graph by an analogous scaling of block entropy functionals defined on the graph. Furthermore, we are able to recast the full set of HV graphs generated by intermittent dynamics into a renormalization-group framework, where the fixed points of its graph-theoretical renormalization-group flow account for the different types of dynamics.We also establish that the nontrivial fixed point of this flow coincides with the tangency condition and that the corresponding invariant graph exhibits extremal entropic properties.

On the forced matching numbers of bipartite graphs

Let G be a graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M, such that S is contained in no other perfect matching of G. This notion has arisen in the study of finding resonance structures of a given molecule in chemistry. Similar concepts have been studied for block designs and graph colorings under the name defining set, and for Latin squares under the name critical set. There is some study of forcing sets of hexagonal systems in the context of chemistry, but only a few other classes of graphs have been considered. For the hypercubes Q(n), it turns out to be a very interesting notion which includes many challenging problems. In this paper we study the computational complexity of finding the forcing number of graphs, and we give some results on the possible values of forcing number for different matchings of the hypercube Q(n). Also we show an application to critical sets in back circulant Latin rectangles. (C) 2003 Elsevier B.V. All rights reserved.

Simplicial Complexes From Graphs Toward Graph Persistence

Persistent homology is a branch of computational topology which uses geometry and topology for shape description and analysis. This dissertation is an introductory study to link persistent homology and graph theory, the connection being represented by various methods to build simplicial complexes from a graph. The methods we consider are the complex of cliques, of independent sets, of neighbours, of enclaveless sets and complexes from acyclic subgraphs, each revealing several properties of the underlying graph. Moreover, we apply the core ideas of persistence theory in the new context of graph theory, we define the persistent block number and the persistent edge-block number.

Synthesis and structural characterization of block and random low molecular weight copolymers composed of L-lactic acid and isosorbide succinate moieties

Isosorbide succinate moieties were incorporated into poly(L-lactide) (PLLA) backbone in order to obtain a new class of biodegradable polymer with enhanced properties. This paper describes the synthesis and characterization of four types of low molecular weight copolymers. Copolymer I was obtained from monomer mixtures of L-lactide, isosorbide, and succinic anhydride; II from oligo(L-lactide) (PLLA), isosorbide, and succinic anhydride; III from oligo(isosorbide succinate) (PIS) and L-lactide; and IV from transesterification reactions between PLLA and PIS. MALDI-TOFMS and 13C-NMR analyses gave evidence that co-oligomerization was successfully attained in all cases. The data suggested that the product I is a random co-oligomer and the products II-IV are block co-oligomers.

Numerical evidence against a conjecture on the cover time of planar graphs

We investigate a conjecture on the cover times of planar graphs by means of large Monte Carlo simulations. The conjecture states that the cover time tau (G(N)) of a planar graph G(N) of N vertices and maximal degree d is lower bounded by tau (G(N)) >= C(d)N(lnN)(2) with C(d) = (d/4 pi) tan(pi/d), with equality holding for some geometries. We tested this conjecture on the regular honeycomb (d = 3), regular square (d = 4), regular elongated triangular (d = 5), and regular triangular (d = 6) lattices, as well as on the nonregular Union Jack lattice (d(min) = 4, d(max) = 8). Indeed, the Monte Carlo data suggest that the rigorous lower bound may hold as an equality for most of these lattices, with an interesting issue in the case of the Union Jack lattice. The data for the honeycomb lattice, however, violate the bound with the conjectured constant. The empirical probability distribution function of the cover time for the square lattice is also briefly presented, since very little is known about cover time probability distribution functions in general.

Universal and nonuniversal contributions to block-block entanglement in many-fermion systems

We calculate the entanglement entropy of blocks of size x embedded in a larger system of size L, by means of a combination of analytical and numerical techniques. The complete entanglement entropy in this case is a sum of three terms. One is a universal x- and L-dependent term, first predicted by Calabrese and Cardy, the second is a nonuniversal term arising from the thermodynamic limit, and the third is a finite size correction. We give an explicit expression for the second, nonuniversal, term for the one-dimensional Hubbard model, and numerically assess the importance of all three contributions by comparing to the entropy obtained from fully numerical diagonalization of the many-body Hamiltonian. We find that finite-size corrections are very small. The universal Calabrese-Cardy term is equally small for small blocks, but becomes larger for x > 1. In all investigated situations, however, the by far dominating contribution is the nonuniversal term stemming from the thermodynamic limit.

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.

On the resilience of long cycles in random graphs

In this paper we determine the local and global resilience of random graphs G(n,p) (p >> n(-1)) with respect to the property of containing a cycle of length at least (1 - alpha)n. Roughly speaking, given alpha > 0, we determine the smallest r(g) (G, alpha) with the property that almost surely every subgraph of G = G(n,p) having more than r(g) (G, alpha)vertical bar E(G)vertical bar edges contains a cycle of length at least (1 - alpha)n (global resilience). We also obtain, for alpha < 1/2, the smallest r(l) (G, alpha) such that any H subset of G having deg(H) (v) larger than r(l) (G, alpha) deg(G) (v) for all v is an element of V(G) contains a cycle of length at least (1 - alpha)n (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.

Gibbs random graphs on point processes

Consider a discrete locally finite subset Gamma of R(d) and the cornplete graph (Gamma, E), with vertices Gamma and edges E. We consider Gibbs measures on the set of sub-graphs with vertices Gamma and edges E` subset of E. The Gibbs interaction acts between open edges having a vertex in common. We study percolation properties of the Gibbs distribution of the graph ensemble. The main results concern percolation properties of the open edges in two cases: (a) when Gamma is sampled from a homogeneous Poisson process; and (b) for a fixed Gamma with sufficiently sparse points. (c) 2010 American Institute of Physics. [doi:10.1063/1.3514605]

Novel blue emitters based on pi-conjugated block copolymers

A series of new phenyl-based conjugated copolymers has been synthesized and investigated by vibrational and photoluminescence spectroscopy (PL). The materials are: poly( 1,4-phenylene-alt-3,6-pyridazine) (COP-PIR), poly(9,9-dioctylfluorene)-co-quaterphenylene (COP-PPP) and poly[(1,4-phenylene-alt-3,6-pyridazine)-co-(1,4-phenylene-alt-9,9-dioctylfluorene)] (COP-PIR-FLUOR), with 3.5% of fluorene. COP-PPP and COP-PIR-FLUOR have high fluorescence quantum yields in solution. Infrared and Raman spectra were used to check the chemical structure of the compounds. The copolymers exhibit blue emission ranging front 2.8 to 3.6 eV when excited at E(exc)=4.13 eV. Stokes-shift Values were estimated on pristine samples in their condensed state from steady-state PL-emission and PL-excitation spectra. They suggest a difference in the torsional angle between the molecular configuration of the polymer blocks at the absorption and PL transitions and also in the photoexcitation diffusion. Additionally, the time-resolved PL of these materials has been investigated by using 100 fs laser pulses at E(exc)=4.64 eV and a streak camera. Results show very fast biexponential kinetics for the two fluorene-based polymers with decay times below 300 ps indicating both intramolecular, fast radiative recombination and migration of photogenerated electron-hole pairs. By contrast, the PL of COP-PIR is less intense and longer lived, indicating that excitons are confined to the chains in this polymer. (C) 2008 Elsevier B.V. All rights reserved.