On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

A necessary and sufficient condition for acyclic graphs

This letter gives a new necessary and sufficient condition to determine whether a directed graph is acyclic.

Improvement On Brooks Chromatic Bound For A Class Of Graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5−e and H) as an induced subgraph and if Δ(G)greater-or-equal, slanted6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)greater-or-equal, slanted6 can not be non-trivially relaxed and the graph K5−e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5−e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)greater-or-equal, slanted9 and d(G)<Δ(G), then χ(G)<Δ(G).

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Degradation of lignin and other 14C-labelled compounds in compost and soil with an emphasis on white-rot fungi

Puu, ruohokasvit ja näistä tehdyt tuotteet kuten mekaanisesta massasta valmistettu sanomalehtipaperi sisältävät ligniiniä, joka hajoaa yleensä hyvin hitaasti luonnossa. Valkolahosienet hajottavat ligniiniä tehokkaimmin, ja koska niiden tuottamat entsyymit hajottavat myös muita vaikeasti hajoavia yhdisteitä, voidaan valkolahosienten avulla mahdollisesti puhdistaa saastuneita maita. Tässä työssä haluttiin selvittää, säilyttävätkö valkolahosienet (Abortiporus biennis, Bjerkandera adusta, Dichomitus squalens, Phanerochaete chrysosporium, Phanerochaete sordida, Phlebia radiata, Pleurotus ostreatus, Trametes hirsuta ja Trametes versicolor) aktiivisuutensa ja kasvavatko ne maassa. Aktiivisuutta mitattiin seuraamalla sienten synteettisen ligniinin (14C-DHP) hajotuskykyä. T. versicolor (silkkivyökääpä) osoittautui tehokkaimmaksi ligniinin hajottajaksi ja sen pentakloorifenolin (PCP) hajotuskykyä tutkittiin erillisessä kokeessa. Entiset tai pitkään käytössä olleet saha-alueet ovat yhä saastuneet puun käsittelyaineista peräisin olevilla kloorifenoleilla. Biohajoavien muovien kehitystyö sekä kompostoinnin yleistyminen jätteiden käsittelymenetelmänä ovat luoneet tarpeen materiaalien biohajoavuuden määrittämiseen. Euroopan standardisoimisjärjestön (CEN) kontrolloidussa kompostitestissä biohajoavuus määritetään materiaalin hajoamisen aikana muodostuvan hiilidioksidin perusteella. Hiilidioksidin tuotto mitataan sekä näytettä sisältävästä kompostista että kompostista ilman näytettä, ja tällöin oletetaan, että kompostin orgaaninen aines molemmissa komposteissa (tausta) tuottaa yhtä paljon hiilidioksidia. Testin puutteeksi saattaa osoittautua kompostissa tai maassa esiintyvä "priming effect". Tällä tarkoitetaan materiaalin lisäämisen jälkeen esiintyvää epänormaalin suurita tai pientä hiilidioksidin muodostusta, minkä seurauksena testin tulosksena saatava biohajoavuus on virheellinen. Ligniinin hajotessa muodostuu enemmän humusta kuin hiilidioksidia, koska ligniini on humuksen tärkein lähtöaine. Näin ollen ligniiniä sisältävät paperituotteet saattavat testin mukaan vaikuttaa biologisesti hajoamattomilta. Valkolahosienet hajottivat 4-23% ligniinistä hiilidioksidiksi ja T. versicolor 29% PCP:sta. Kompostissa ligniini hajosi hiilidioksidiksi 58°C:ssa huomattavasti vähemmän (8%) kuin lämpötiloissa 35°C ja 50°C (23-24%). Kompostin todennäköisesti tärkeimpien ligniinin hajottajien, termofiilisten sienten, tyypillinen optimilämpötila on 45°C, eivätkä ne ole enää aktiivisia 58°C:ssa. Sekä maassa että kompostissa ligniini sitoutui kuitenkin suurimmaksi osaksi humukseen. Valkolahosienet hajottivat sekä humukseen sitoutunutta ligniiniä että PCP:ia, mutta kompostin sekapopulaatio ei tähän pystynyt, ja ligniiniä sitoutui humukseen yhä enemmän kompostoinnin aikana. T. versicolor hajotti PCP:ia tehokkaasti, eikä se tuottanut myrkyllisiä kloorianisoleja, joita jotkut valkolahosienet saattavat muodostaa kloorifenoleista. Priming effect ilmiötä tutkittiin eri ikäisissä ja kypsyydeltään erilaisissa komposteissa. Kompostit erosvat toisistaan myös hajoamattoman jätteen määrän ja mikrobipopulaation suhteen. Negatiivinen priming effect havaittiin kaikissa epästabiileissa komposteissa (ikä enintään 6 kk), ja sen lisäksi yhdessä näistä komposteista positiivinen priming effect kokeen lopussa. Stabiileissa komposteissa (ikä vähintään 6 kk) ilmiötä ei sen sijaan havaittu. Epästabiileissa komposteissa biohajoavuudelle saadut tulokset eivät siis ole luotettavia. Työn tulosten perusteella valkolahosienet, ja erityisesti T. versicolor, ovat lupaavia saastuneen maan puhdistukseen, joskin sienirihmaston mahdollisuudet säilyä aktiivisena maan alkuperäisen mikrobipopulaation kanssa täytyy vielä selvittää. Kompostin sekapopulaatio, joka ei sisällä valkolahosieniä, hajotti ligniiniä yllättävän tehokkaasti termofiilisille sienille sopivissa lämpötiloissa, vaikka ligniini sitoutuikin pääasiallisesti humukseen. Kompostin kypsyys osoittautui tärkeäksi tekijäksi kontrolloidun kompostitestin onnistumisen kannalta. Priming effect ilmiön välttämiseksi on varmistettava, että testissä käytetty komposti on riittävän kypsä. Kompostien mikrobipopulaation koostumusta kompostoinnin eri vaiheissa tulisi tarkemmin selvittää, koska stabiilien ja epästabiilien kompostien ero aiheutui todennäköisesti populaatioiden rakenteessa vallitsevista eroista. Näin myös priming effect ilmiön syyt voitaisiin selittää paremmin.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

A simple biosynthetic method for the preparation of glycerol-labelled phosphatidylcholine

A convenient method is described for the preparation of glycerol-labelled phosphatidylcholine with very high specific activity. It involves germination of soybean seeds in the dark at 37°C for 48 h in the presence of labelled glycerol, followed by extraction and purification of the phospholipid.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Vibrational spectra of hydrazine carbothioamide and its 15N- and D-labelled species

Raman and infrared spectra of hydrazine carbothioamide (HCTA) and its three 15N-labelled molecules (H2N NH CS15NH2, H2 15N15NHCSNH2 and H2 15N15NHCS15NH2) and their deuterated compounds have been obtained. A complete normal coordinate analysis of HCTA has been made and revised assignments are presented. The factor group splittings of HCTA have been interpreted.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.

A note on the Hadwiger number of circular arc graphs

The intention of this note is to motivate the researchers to study Hadwiger's conjecture for circular arc graphs. Let η(G) denote the largest clique minor of a graph G, and let χ(G) denote its chromatic number. Hadwiger's conjecture states that η(G)greater-or-equal, slantedχ(G) and is one of the most important and difficult open problems in graph theory. From the point of view of researchers who are sceptical of the validity of the conjecture, it is interesting to study the conjecture for graph classes where η(G) is guaranteed not to grow too fast with respect to χ(G), since such classes of graphs are indeed a reasonable place to look for possible counterexamples. We show that in any circular arc graph G, η(G)less-than-or-equals, slant2χ(G)−1, and there is a family with equality. So, it makes sense to study Hadwiger's conjecture for this family.

On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), a(i) + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of C can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes. An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We give an O(bw . n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Delta) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Delta) bandwidth. Thus we have: 1. cub(G) <= 3 Delta - 1, if G is an AT-free graph. 2. cub(G) <= 2 Delta + 1, if G is a circular-arc graph. 3. cub(G) <= 2 Delta, if G is a cocomparability graph. Also for these graph classes, there axe constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Delta) width. We can thus generate the cube representation of such graphs in O(Delta) dimensions in polynomial time.