The P3 Intersection Graph

We define a new graph operator called the P3 intersection graph, P3(G)- the intersection graph of all induced 3-paths in G. A characterization of graphs G for which P-3 (G) is bipartite is given . Forbidden subgraph characterization for P3 (G) having properties of being chordal , H-free, complete are also obtained . For integers a and b with a > 1 and b > a - 1, it is shown that there exists a graph G such that X(G) = a, X(P3( G)) = b, where X is the chromatic number of G. For the domination number -y(G), we construct graphs G such that -y(G) = a and -y (P3(G)) = b for any two positive numbers a > 1 and b. Similar construction for the independence number and radius, diameter relations are also discussed.

The Edge C4 Graph of a Graph

Abstract. The edge C4 graph E4(G) of a graph G has all the edges of Gas its vertices, two vertices in E4(G) are adjacent if their corresponding edges in G are either incident or are opposite edges of some C4. In this paper, characterizations for E4(G) being connected, complete, bipartite, tree etc are given. We have also proved that E4(G) has no forbidden subgraph characterization. Some dynamical behaviour such as convergence, mortality and touching number are also studied

GALLAI AND ANTI-GALLAI GRAPHS OF A GRAPH

Abstract. The paper deals with graph operators-the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H-free for any finite graph H. The case of complement reducible graphs-cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.

Studies on some graph operators and related topics

Department of Mathematics, Cochin University of Science and Technology

Studies on Some Graph Classes

Department of Mathematics, Cochin University of Science and Technology

Studies on some generalizations of line graph and the power domination problem in graphs

Department of Mathematics, Cochin University of Science and Technology

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

Median Sets and Median Number of a Graph

A profile is a finite sequence of vertices of a graph. The set of all vertices of the graph which minimises the sum of the distances to the vertices of the profile is the median of the profile. Any subset of the vertex set such that it is the median of some profile is called a median set. The number of median sets of a graph is defined to be the median number of the graph. In this paper, we identify the median sets of various classes of graphs such as Kp − e, Kp,q forP > 2, and wheel graph and so forth. The median numbers of these graphs and hypercubes are found out, and an upper bound for the median number of even cycles is established.We also express the median number of a product graph in terms of the median number of their factors.

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

Content aggregation on knowledge bases using graph clustering

Recently, research projects such as PADLR and SWAP have developed tools like Edutella or Bibster, which are targeted at establishing peer-to-peer knowledge management (P2PKM) systems. In such a system, it is necessary to obtain provide brief semantic descriptions of peers, so that routing algorithms or matchmaking processes can make decisions about which communities peers should belong to, or to which peers a given query should be forwarded. This paper proposes the use of graph clustering techniques on knowledge bases for that purpose. Using this clustering, we can show that our strategy requires up to 58% fewer queries than the baselines to yield full recall in a bibliographic P2PKM scenario.

Effects of fertilizer type and rate on partitioning of soil organic matter into pools of different stability

Type and rate of fertilizers influence the level of soil organic carbon (Corg) and total nitrogen (Nt) markedly, but the effect on C and N partitioning into different pools is open to question. The objectives of the present work were to: (i) quantify the impact of fertilizer type and rate on labile, intermediate and passive C and N pools by using a combination of biological, chemical and mathematical methods; (ii) explain previously reported differences in the soil organic matter (SOM) levels between soils receiving farmyard manure with or without biodynamic preparations by using Corg time series and information on SOM partitioning; and (iii) quantify the long-term and short-term dynamics of SOM in density fractions and microbial biomass as affected by fertilizer type and rate and determine the incorporation of crop residues into labile SOM fractions. Samples were taken from a sandy Cambisol from the long-term fertilization trial in Darmstadt, Germany, founded in 1980. The nine treatments (four field replicates) were: straw incorporation plus application of mineral fertilizer (MSI) and application of rotted farmyard manure with (DYN) or without (FYM) addition of biodynamic preparations, each at high (140 – 150 kg N ha-1 year-1; MSIH, DYNH, FYMH), medium (100 kg N ha-1 year-1; MSIM, DYNM, FYMM) and low (50 – 60 kg N ha-1 year-1; MSIL, DYNL, FYML) rates. The main findings were: (i) The stocks of Corg (t ha-1) were affected by fertilizer type and rate and increased in the order MSIL (23.6), MSIM (23.7), MSIH (24.2) < FYML (25.3) < FYMM (28.1), FYMH (28.1). Stocks of Nt were affected in the same way (C/N ratio: 11). Storage of C and N in the modelled labile pools (turnover times: 462 and 153 days for C and N, respectively) were not influenced by the type of fertilizer (FYM and MSI) but depended significantly (p ≤ 0.05) on the application rate and ranged from 1.8 to 3.2 t C ha 1 (7 – 13% of Corg) and from 90 to 140 kg N ha-1 (4-5% of Nt). In the calculated intermediate pool (C/N ratio 7), stocks of C were markedly higher in FYM treatments (15-18 t ha-1) compared to MSI treatments (12-14 t ha-1). This showed that differences in SOM stocks in the sandy Cambisol induced by fertilizer rate may be short-lived in case of changing management, but differences induced by fertilizer type may persist for decades. (ii) Crop yields, estimated C inputs (1.5 t ha-1 year-1) with crop residue, microbial bio¬mass C (Cmic, 118 – 150 mg kg-1), microbial biomass N (17 – 20 mg kg-1) and labile C and N pools did not differ significantly between FYM and DYN treatments. However, labile C increased linearly with application rate (R2 = 0.53) from 7 to 11% of Corg. This also applied for labile N (3.5 to 4.9% of Nt). The higher contents of Corg in DYN treatments existed since 1982, when the first sampling was conducted for all individual treatments. Contents of Corg between DYN and FYM treatments con-verged slightly since then. Furthermore, at least 30% of the difference in Corg was located in the passive pool where a treatment effect could be excluded. Therefore, the reported differences in Corg contents existed most likely since the beginning of the experiment and, as a single factor of biodynamic agriculture, application of bio-dynamic preparations had no effect on SOM stocks. (iii) Stocks of SOM, light fraction organic C (LFOC, ρ ≤ 2.0 g cm-3), light fraction organic N and Cmic decreased in the order FYMH > FYML > MSIH, MSIL for all sampling dates in 2008 (March, May, September, December). However, statistical significance of treatment effects differed between the dates, probably due to dif-ferences in the spatial variation throughout the year. The high proportion of LFOC on total Corg stocks (45 – 55%) highlighted the importance of selective preservation of OM as a stabilization mechanism in this sandy Cambisol. The apparent turnover time of LFOC was between 21 and 32 years, which agreed very well with studies with substantially longer vegetation change compared to our study. Overall, both approaches; (I) the combination of incubation, chemical fractionation and simple modelling and (II) the density fractionation; provided complementary information on the partitioning of SOM into pools of different stability. The density fractionation showed that differences in Corg stocks between FYM and MSI treatments were mainly located in the light fraction, i.e. induced by higher recalcitrance of the organic input in the FYM treatments. Moreover, the use of the combination of biological, chemical and mathematical methods indicated that effects of fertilizer rate on total Corg and Nt stocks may be short-lived, but that the effect of fertilizer type may persist for longer time spans in the sandy Cambisol.

Web Graph

Slides and an essay on the Web Graph, search engines and how Google calculates Page Rank