bluuebunny/crossref_metadata_2025 huggingface dataset:
Genus of cartesian products of regular bipartite graphs
Authors: Pisanski Tomaž
Published: May 2007

Let G(n, d) denote a connected regular bipartite graph on 2n vertices and of degree d. It is proved that any Cartesian product G(n, d) × G1(n1, d1) × G2(n2, d2) × ⃛ × Gm(nm, dm), such that max {d1, d2,…, dm} ≤ d ≤ d1 + d2 + ⃛ + dm, has a quadrilateral embedding, thereby establishing its genus, and thereby generalizing a result of White. It is also proved that if G is any connected bipartite graph of maximum degree D, if Qm is the m‐cube graph, and if m ≥ D then G × Qm has a quadrilateral embedding.
Bigraphs versus digraphs via matrices
Authors: Brualdi Richard A. , Harary Frank , Miller Zevi
Published: May 2007

It was observed by Dulmage and Mendelsohn in their work on matrix reducibility that there is a one‐to‐one correspondence between bigraphs and digraphs determined by the utilization of the adjacency matrix. In this semiexpository paper we explore the interaction between this correspondence and a theory of matrix decomposability that is developed in several different articles. These results include: (a) a characterization of those bipartite graphs that can be labeled so that the resulting digraph is symmetric; (b) a criterion for the bigraph of a symmetric digraph to be connected; (c) a necessary and sufficient condition for a square binary matrix to be fully indecomposable in terms of its associated bigraph, and (d) matrix criteria for a digraph to be strongly, unilaterally, or weakly connected. We close with an unsolved extermal problem on the number of components of the bigraph of various orientations of a given graph. This leads to new amusing characterizations of trees and bigraphs.

Dedicated to the graph‐theoretic partnership of Lloyd Dulmage and Nathan Mendelsohn.
n‐cubes and median graphs
Authors: Mulder Martyn
Published: May 2007

The n‐cube is characterized as a connected regular graph in which for any three vertices u, v, and w there is a unique vertex that lies simultaneously on a shortest (u, v)‐path, a shortest (v, w)‐path, and a shortest (w, u)‐path.
Condition for a tournament score sequence to be simple
Authors: Avery Peter
Published: May 2007

The condition is given for a (tournament) score sequence to belong to exactly one tournament.
Locally petersen graphs
Authors: Hall J. I.
Published: May 2007

A graph Γ is locally Petersen if, for each point t of Γ, the graph induced by Γ on all points adjacent to t is isomorphic to the Petersen graph. We prove that there are exactly three isomorphism classes of connected, locally Petersen graphs and further characterize these graphs by certain of their parameters.
An upper bound for the path number of a graph
Authors: Donald Alan
Published: May 2007

The path number of a graph G, denoted p(G), is the minimum number of edge‐disjoint paths covering the edges of G. Lovász has proved that if G has u odd vertices and g even vertices, then p(G) ≤ 1/2 u + g ‐ 1 ≤ n ‐ 1, where n is the total number of vertices of G. This paper clears up an error in Lovász's proof of the above result and uses an extension of his construction to show that p(G) ≤ 1/2 u + [3/4g] ≤ [3/4n].
Number of labeled 4‐regular graphs
Authors: Read R. C. , Wormald N. C.
Published: May 2007

Several operations on 4‐regular graphs and pseudographs are analyzed and equations are obtained relating the numbers of these graphs on given numbers of labeled points. These equations are used recursively to find the numbers of 4‐regular graphs on up to 13 labeled points.
A ramsey‐theoretic result involving chromatic numbers
Authors: Burr Stefan A.
Published: May 2007

The following result is proved. A graph G can be expressed as the edge‐disjoint union of k graphs having chromatic numbers no greater than m1,…,mk, respectively, iff χ(G) ≤ m1…mk.
Realizability of p‐point graphs with prescribed minimum degree, maximum degree, and line connectivity
Authors: Boesch F. T. , Suffel C. L.
Published: May 2007

It is well known that certain graph‐theoretic extremal questions play a central role in the study of communication network vulnerability. Herein we consider a generalization of some of the classical results in this area. We define a (p, Δ, δ, λ) graph as a graph having p points, maximum degree Δ, minimum degree Δ, and line connectivity λ. An arbitrary quadruple of integers (a, b, c, d) is called (p, Δ, δ, λ) realizable if there is a (p, Δ, δ, λ) graph with p = a, Δ = b, Δ = c, and λ = d. Necessary and sufficient conditions for a quadruple to be (p, Δ, δ, λ) realizable are derived.
The number of connected sparsely edged graphs. III. Asymptotic results
Authors: Wright E. M.
Published: May 2007

The number of connected graphs on n labeled points and q lines (no loops, no multiple lines) is f(n,q). In the first paper of this series I showed how to find an (increasingly complicated) exact formula for f(n,n+k) for general n and successive k. The method would give an asymptotic approximation to f(n,n+k) for any fixed k as n → ∞. Here I find this approximation when k = o(n1/3), a much more difficult matter. The problem of finding an approximation to f(n,q) when q > n + Cn1/3 and (2 q/n) ‐ log n → ‐ ∞ is open.
Cycles with a chord are graceful
Authors: Delorme C. , Maheo M. , Thuillier H. , Koh K. M. , Teo H. K.
Published: May 2007

In this paper, we prove that every cycle plus a chord is graceful, thus answering a conjecture of R. Bodendiek, H. Schumacher, and H. Wegner.
Matchings and walks in graphs
Authors: Godsil C. D.
Published: May 2007

The matching polynomial α(G, x) of a graph G is a form of the generating function for the number of sets of k independent edges of G. in this paper we show that if G is a graph with vertex v then there is a tree T with vertex w such that \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{\alpha (G\backslash v, x)}}{{\alpha (G, x)}} = \frac{{\alpha (T\backslash w, x)}}{{\alpha (T, x)}}. $\end{document}

This result has a number of consequences. Here we use it to prove that α(G\v, 1/x)/xα(G, 1/x) is the generating function for a certain class of walks in G. As an application of these results we then establish some new properties of α(G, x).
Hamiltonian line graphs
Authors: Brualdi Richard A. , Shanny Robert F.
Published: May 2007

Sufficient conditions on the degrees of a graph are given in order that its line graph have a hamiltonian cycle.
Some arrowing results for trees versus complete graphs
Authors: Polimeni Albert D. , Straight H. JosephS , Yellen Jay
Published: May 2007

For an arbitrary tree T of order m and an arbitrary positive integer n, Chvátal proved that the Ramsey number r(T, Kn) = 1 + (m − 1) (n − 1). for graphs G, G1, and G2, we say that G arrows G1 and G2, written G → (G1, G2), if for every factorization G = R ⊕ B, either G1 is a subgraph of R or G2 is a subgraph of B. it is shown that (i) for each l ≥ 2, K1+ (m−1)(n−1) −E(K1) → (T, Kn) for m ≥ 2/ − 1 and n ≥ 2; (ii) K1 +,(m −1)(n −1) − E(H) → (T, Kn), where H is any tree of order m − 1, m ≥ 3 and n ≥ 2. It is further shown that result (i) is sharp with respect to the inequality m ≥ 2/− 1; in particular, examples are given to show that K1 + (2l−3)(n−1) E(K1) ↛ (P21−2, Kn) for all n ≥ 2, where P21−2 denotes the path of order 21 − 2. Also result (ii) is sharp with respect to the order of H; examples aregiven to show that K1 + (m−1)(n−1)− E(K(1, m − 1)) ↛(T, Kn)for any tree T of order m and any n ≥ 2.
Which rational numbers are binding numbers?
Authors: Kane V. G. , Mohanty S. P. , Straus E. G.
Published: May 2007

The concept of the binding number of a graph was introduced by Woodall in 1973. in this paper we characterize the set Fn of all pairs (a, b) of integers such that there is a graph G with n vertices and binding number a/b that has a realizing set of b vertices.
Generalized line graphs
Authors: Cvetkovic̀ Dragoš , Doob Michael , Simic̀ Slobodan
Published: May 2007

Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation and construction of the 31 minimal nongeneralized line graphs, a Krausz‐type covering characterization, and Whitney‐type theorems on isomorphisms and automorphisms.
Paley graphs satisfy all first‐order adjacency axioms
Authors: Blass Andreas , Exoo Geoffrey , Harary Frank
Published: May 2007

A graph satisfies Axiom n if, for any sequence of 2n of its points, there is another point adjacent to the first n and not to any of the last n. We show that, for each n, all sufficiently large Paley graphs satisfy Axiom n. From this we conclude at once that several properties of graphs are not first order, including self‐complementarity and regularity.
Domination‐balanced graphs
Authors: Payan Charles , Xuong Nguyen Huy
Published: May 2007

A set D of vertices in a graph is said to be a dominating set if every vertex not in D is adjacent to some vertex in D. The domination number β(G) of a graph G is the size of a smallest dominating set. G is called domination balanced if its vertex set can be partitioned into β(G) subsets so that each subset is a smallest dominating set of the complement G of G. The purpose of this paper is to characterize these graphs.
Edge‐reconstruction of 4‐connected planar graphs
Authors: Fiorini S. , Lauri J.
Published: May 2007

The object of this paper is to show that 4‐connected planar graphs are uniquely determined from their collection of edge‐deleted subgraphs.
Note on the reconstruction of infinite graphs with a fixed finite number of components
Authors: Andreae Thomas
Published: May 2007

For every positive integer c, we construct a pair Gc, Hc of infinite, nonisomorphic graphs both having exactly c components such that Gc and Hc are hypomorphic, i.e., Gc and Hc have the same families of vertex‐deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G1, H1 is an example for a pair of non‐isomorphic, hypomorphic, connected graphs also having connected complements—a property not shared by any of the previously known counterexamples to the reconstruction conjecture for infinite graphs.
A class of geodetic blocks
Authors: Cook R. J. , Pryce D. G.
Published: May 2007

A new class of geodetic blocks is constructed and it is shown how these are derived from Plesnik's geodetic homeomorphs of complete graphs.
On the toroidal thickness of graphs
Authors: Anderson Ian
Published: May 2007

The toroidal thickness t1(G) of a graph G is the minimum value of k such that G is the union of k graphs each of which is embeddable on a torus. We find t1(Gm), where Gm is the graph obtained from the complete graph Km by removing a Hamiltonian cycle, and we show that t1(Kn(3)) = [1/2n] for many values of n. The method of approach involves the construction of sets of triples related to Skolem triples.
4‐valent graphs
Authors: Enns T. C.
Published: May 2007

Let {pk}k≥2, k≠4 be a sequence of non‐negative integers which satisfies 8 + Σk≥3(k — 4)pk = 0. Then there exists an integer p4 such that there exists a 2‐connected planar graph with exactly pk k‐gons as faces for all k ≥ 2. This paper determines all such p4 when pk = 0 for k ≥ 5 and determines that there is a constant C ≥ 1 such that for some m ≤ p2 + 1/4p3 + C, there exists a 2‐connected planar graph with exactly pk faces for each p4 = m + 2w, w a positive integer. When there exists at least one odd k ≥ 3 for which pk ≠ 0, the coefficient 2 of w in the above equation may be replaced by 1. These conclusions do not hold if the coefficients of p2 and p3 are any smaller than 1 and 1/4, respectively.
On the berge—sauer conjecture
Authors: Parthasarathy K. R. , Sridharan S.
Published: May 2007

It is proved that a simple 4‐regular graph without K1,3 as an induced subgraph has a 3‐regular subgraph.
More rotation numbers for complete bipartite graphs
Authors: Bollobás Béla , Cockayne E. J.
Published: May 2007

Let G be a simple undirected graph which has p vertices and is rooted at x. Informally, the rotation number h(G, x) of this rooted graph is the minimum number of edges in a p vertex graph H such that for each vertex v of H, there exists a copy of G in H with the root x at v. In this article we calculate some rotation numbers for complete bipartite graphs, and thus greatly extend earlier results of Cockayne and Lorimer.
A 1‐factorization of the line graphs of complete graphs
Authors: Alspach Brian
Published: May 2007

A 1‐factorization is constructed for the line graph of the complete graph Kn when n is congruent to 0 or 1 modulo 4.
Cyclically 5‐edge‐connected cubic planar graphs and shortness coefficients
Authors: Owens P. J.
Published: May 2007

It is shown that some classes of cyclically 5‐edge‐connected cubic planar graphs with only one type of face besides pentagons contain non‐Hamiltonian members and have shortness coefficients less than unity.
Randomly antitraceable digraphs
Authors: Fink John Frederick
Published: May 2007

An antipath in a digraph is a semipath containing no (directed) path of length 2. A digraph D is randomly antitraceable if for each vertex v of D, any antipath beginning at v can be extended to a hamiltonian antipath beginning at v. In this paper randomly antitraceable digraphs are characterized.
Diagonal Ramsey numbers for small graphs
Authors: Burr S. A.
Published: May 2007

The (generalized) Ramsey number r(G) is determined for all 113 graphs with no more than six lines and no isolated points. While few proofs are given, information is given which should be sufficient to reconstruct them in most cases.
Vertex coverings by monochromatic paths and cycles
Authors: Gyárfás A.
Published: May 2007

We survey some results on covering the vertices of 2‐colored complete graphs by two paths or by two cycles of different color. We show the role of these results in determining path Ramsey numbers and in algorithms for finding long monochromatic paths or cycles in 2‐colored complete graphs.
New lower bounds of some diagonal Ramsey numbers
Authors: Guldan Filip , Tomasta Pavel
Published: May 2007

A new construction of self‐complementary graphs containing no K10 or K11 is described. This construction gives the Ramsey number lower bounds r(10,10) ≧ 458 and r(11,11) ≧ 542.
On 4‐cycles in random bipartite tournaments
Authors: Bollobés Béla , Frank Ove , KarońSki Michał
Published: May 2007

We consider a random m by n bipartite tournament Tmn consisting of mn independent random arcs which have a common probability p of being directed from the m part to the n part. We determine the expected value and variance of the number of 4‐cycles in Tmn and the probability that Tmn has no cycles. An asymptotic expression for this probability is also given when p = 1/2 and m and n tend to infinity.
On the genus of five‐ and six‐regular graphs
Authors: Proulx Viera Krňanová
Published: May 2007

This paper shows how to construct infinitely many regular graphs of degrees five and six having given genus γ > 0, which settles favorably Conjecture 1 stated by T. W. Tucker. Tucker has shown that there are infinitely many regular graphs of degrees four and three of arbitrary given genus (Theorem 1). He also proved that the number of regular graphs of degree greater than six embeddable in a given surface is finite (Corollary to Proposition 1). The case of the regular graphs of degrees six and five was left unanswered (Conjecture 1). This paper also shows a new way of constructing infinitely many regular graphs of degrees three and four of arbitrary genus γ > 0.
Arc‐disjoint arborescences of digraphs
Authors: Mao‐cheng Cai
Published: May 2007

The purpose of this paper is to give a necessary and sufficient condition for a digraph G to contain k arc‐disjoint arborescences so that the number rooted at each vertex x of G lies in some prescribed interval which depends on x.
Graph decomposition with applications to subdivisions and path systems modulo k
Authors: Thomassen Carsten
Published: May 2007

The existence of a function α(k) (where k is a natural number) is established such that the vertex set of any graph G of minimum degree at least α(k) has a decomposition A ∪ B ∪ C such that G(A) has minimum degree at least k, each vertex of A is joined to at least k vertices of B, and no two vertices of B are separated by fewer than k vertices in G(G ∪ C). This is applied to prove the existence of subdivisions of complete bipartite graphs (complete graphs) with prescribed path lengths modulo k in graphs of sufficiently high minimum degree (chromatic number) and path systems with prescribed ends and prescribed lengths modulo k in graphs of sufficiently high connectivity.
Graph dismantling problems
Authors: Dawes A. M. , Florence J. B.
Published: May 2007

Problems involving the dismantling of a digraph (graph) by removal of arcs (edges) are investigated. Some of these problems have good characterizations related to the familiar results about Euler trails, others are NP‐complete.
Packing graphs with odd and even trees
Authors: Fishburn P. C.
Published: May 2007

The Gyárfás‐Lehel tree‐packing conjecture asserts that any sequence T1, T2, …, Tn−1 of trees with 1, 2, …, n ‐ 1 edges packs into the complete graph Kn on n vertices. The present paper examines two conjectures that jointly imply the Gyárfás‐Lehel conjecture: 1. For n even, any T1, T3, …, Tn−1 pack into the half‐complete graph Hn on n vertices.2. For n odd, any T2, T4, …, Tn−1 pack into the half‐complete graph Hn on n vertices.

The Hn are uniquely defined by their degree sequences: Hn and Hn+1 are complements in Kn+1. It is shown that Hn and Tn+1 pack into Hn+2 if Tn+1 is a double star, unimodal triple star, interior‐3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n ≤ 9, so that the Gyárfás‐Lehel conjecture holds for n ≤ 9.
Automorphism properties of embedded graphs
Authors: Hutchinson Joan P.
Published: May 2007

This paper presents some conditions under which every automorphism of a graph, embedded on a surface of positive genus, maps face boundaries of the embedding to face boundaries. These results extend a result of Whitney which provides an analogous, but simpler, condition for planar graphs. The new result is applied to graphs on the torus to obtain a classification of many toroidal vertex‐, edge‐, and face‐transitive graphs.
Vertex‐transitive graphs: Symmetric graphs of prime valency
Authors: Lorimer Peter
Published: May 2007

Let G be a group acting symmetrically on a graph Σ, let G1 be a subgroup of G minimal among those that act symmetrically on Σ, and let G2 be a subgroup of G1 maximal among those normal subgroups of G1 which contain no member except 1 which fixes a vertex of Σ. The most precise result of this paper is that if Σ has prime valency p, then either Σ is a bipartite graph or G2 acts regularly on Σ or G1 | G2 is a simple group which acts symmetrically on a graph of valency p which can be constructed from Σ and does not have more vertices than Σ. The results on vertex‐transitive groups necessary to establish results like this are also included.
Enumeration by frame group and range groups
Authors: Redfield J. Howard
Published: May 2007

Wider extension is here given to the theory developed in an earlier paper, in which the enumeration of certain configurations or combinatorial entities was made to depend on two or more groups (range groups). The present paper recognizes for the first time the essential part played by an additional group, the frame group, which includes all the range groups as subgroups, and which was implicit in the earlier theory as the symmetric group of the degree of the range groups. The use of frame groups which are not symmetric greatly extends the range of application of the theory, and allows its development in terms of abstract groups. By the use of the conjugate sets of the subgroups (both cyclic and noncyclic) of the frame group, instead of merely the conjugate sets of its operations, a complete solution is obtained for the problem (solved only for special cases in the earlier paper) of determining the invariance groups admitted by the various configurations enumerated.
Isomorphic factorizations X: Unsolved problems
Authors: Harary Frank , Robinson Robert W.
Published: May 2007

An isomorphic factorization of a graph is a decomposition into isomorphic edge‐disjoint subgraphs. A number of new and old open problems on isomorphic factorizations are presented along with some existing related results.
Regular factors of regular graphs
Authors: Bollobás B. , Saito Akira , Wormald N. C.
Published: May 2007

Given r ⩾ 3 and 1 ⩽ λ ⩽ r, we determine all values of k for which every r‐regular graph with edge‐connectivity λ has a k‐factor.
Factors in a class of regular digraphs
Authors: Ramanath M. V. S.
Published: May 2007

For the class of 2‐diregular digraphs: (1) We give a simple closed form expression—a power of 2—for the number of difactors. (2) For the adjacency matrices of these graphs, we show an intimate relationship between the permanent and determinant. (3) We give a necessary and sufficient condition for the Cartesian product of two directed circuits to have a difactor with exactly k components thereby generalizing a result of Trotter and Erdöos. Our results also show that a conjecture of Bondy, regarding vertex‐transitive graphs, fails to hold for vertex‐transitive digraphs.
Some observations on the oberwolfach problem
Authors: Alspach Brian , Häggkvist Roland
Published: May 2007

Some results concerning decompositions of Kn, Kn ‐ F(where F denotes a 1‐factor) and complements of a family of special cubic graphs into 2‐factors of the same type are given. In particular, if 2d is a divisor of n, it is shown that Kn ‐ F can be decomposed into 2‐factors each of whose components is a cycle of length 2d.
Isomorphic decomposition of complete graphs into linear forests
Authors: Ruiz Sergio
Published: May 2007

The well‐known theorem of Kirkman states that every complete graph K2n of order 2n is 1‐factorable or, equivalently, is nK2‐decomposable. This result is generalized to any linear forest of size n without isolated vertices.
On the chromatic number of the general Kneser‐graph
Authors: Frankl P.
Published: May 2007

Given integers k, n, 2 < k < n, let us define a graph with vertex set V = {F ⊂{1, 2, …, n}: ∩F = k}, and (F, F') is an edge if |F ∩ F′| ≤ 1. We show that for n > n0(k) the chromatic number of this graph is (k ‐ 1)() + rs, where n = (k ‐ 1)s + r, 0 ≤ r < k ‐ 1.
Unique and faithful embeddings of projective‐planar graphs
Authors: Negami Seiya
Published: May 2007

A graph G is uniquely embeddable in a surface F2 if for any two embeddings f1,f2: G → F2, there exists an isomorphism σ: G → G and a homeomorphism h: F2 → F2 for which h → f1 = f2 σ. A graph G is faithfully embeddable in a surface F2 if G admits an embedding f: G → F2 such that for any isomorphism σ: G → G, there is a homeomorphism h: F2 → F2 with h → f = f → σ. It will be shown that if a projective‐planar graph G is 5‐connected and contains a subdivision of the complete graph K6 as its subgraph, then G is uniquely embeddable in a projective plane, and that moreover if G is not isomorphic to K6, then G is faithfully embeddable in a projective plane.
Do nearly balanced multigraphs have more spanning trees?
Authors: Cheng Ching‐Shui , Masaro Joseph C. , Wong Chi Song
Published: May 2007

Letdithe degree of theith vertex of a mutigraph and λijbe the number of edges between vertexiand vertexj.A multigraph is called nearly balanced if |di−di| ≤1 for alli≠i′ and |λij−λij| for alliand allj,j′ Let be the collection of all the multigraphs withvvertices and e edges. It is shown that for anyv, there is ane* such that if, then any nearly balanced graph in ζv, ehas more spanning trees than any non‐nearly‐balanced graph in ζv, e.
Random hypergraph coloring algorithms and the weak chromatic number
Authors: Schmidt‐Pruzan Jeanette , Shamir Eli , Upfal Eli
Published: May 2007

We present a hypergraph coloring algorithm and analyze its performance in spaces of random hypergrpahs. In these spaces the number of colors used by our algorithm is almost surely within a small constant factor (less than 2) of the weak chromatic number of the hypergraph. This also establishes new upper and lower bounds for the weak chromatic number of uniform hypergraphs.
A generalized construction of chromatic index critical graphs from bipartite graphs
Authors: Plantholt Michael
Published: May 2007

We prove that any graph with maximum degree n which can be obtained by removing exactly 2n ‐ 1 edges from the join K1 + Kn, n is n‐critical. This generalizes special constructions of critical graphs by S. Fiorini and H. P. Yap, and suggests a possible extension of another general construction due to Yap.
Shortness parameters for planar graphs with faces of only one type
Authors: Owens P. J.
Published: May 2007

We construct infinite sequences of non‐Hamiltonian graphs and use them to show that the shortness exponent (or, in some cases, the shortness coefficient) is less than one for many classes of 3‐connected planar graphs whose faces are all r‐gons and whose vertices are all p‐valent or q‐valent, where p < q. Three of the five possible values of (r, p) are considered, namely (4.3). (3,3), and (3,4), in conjunction with most of the possible corresponding values of q.
On graphs with prescribed median I
Authors: Hendry G. R. T.
Published: May 2007

The distance of a vertex u in a connected graph H is the sum of all the distances from u to the other vertices of H. The median M(H) of H is the subgraph of H induced by the vertices of minimum distance. For any graph G, let f(G) denote the minimum order of a connected graph H satisfying M(H) ≅ G. It is shown that if G has n vertices and minimum degree δ then f(G) ⩽ 2n − δ + 1. Graphs having both median and center prescribed are constructed. It is also shown that if the vertices of a Kr are removed from a graph H, then at most r components of the resulting graph contain median vertices of H.
Lower‐bounds on the connectivities of a graph
Authors: Esfahanian Abdol H.
Published: May 2007

This article presents a study of the connectivities of a graph as a function of other graph parameters such as the number of vertices, the maximum degree, and the diameter. As a result, lower‐bounds on the connectivities of a graph as a function of these parameters are computed. These bounds could serve as sufficient conditions for a graph to be h‐edge‐connected or k‐connected. Consequently, the connectivity characteristics of many of the densest known graphs are determined.
The crossing number of K1,3,n and K2,3,n
Authors: Asano Kouhei
Published: May 2007

In this article, we will determine the crossing number of the complete tripartite graphs K1,3,n and K2,3,n. Our proof depends on Kleitman's results for the complete bipartite graphs [D. J. Kleitman, The crossing number of K5,n. J. Combinatorial Theory 9 (1970) 315‐323].
Bipartite density and the independence ratio
Authors: Locke Stephen C.
Published: May 2007

If a 3‐regular graph has bipartite density b and independence ratio i, then i ≥ (3b − 1)/4. A construction demonstrates that this is best possible for all admissible values of b.
Maximum matchings in a regular graph of specified connectivity and bounded order
Authors: Katerinis P.
Published: May 2007

Upper bounds are placed on the order of a k‐regular m‐connected graph G that produce a lower bound on the number of independent edges in G. As a corollary, we obtain the order of a smallest k‐regular m‐connected graph which has no 1‐factor.
The bichromaticity of cylinder graphs and torus graphs
Authors: Pritikin Dan
Published: May 2007

The bichromaticity of a bipartite graph B is defined as the maximum value of r + s for which B has the complete bipartite graph Kr, s as a homomorphic image. We determine the bichromaticity of any bipartite cylinder graph C2n × Pm or torus graph C2n × C2m. In the process, we disprove a conjecture of Harary, Hsu, and Miller [2].
Analysis of erlotinib and its metabolites in rat tissue sections by MALDI quadrupole time‐of‐flight mass spectrometry
Authors: Signor Luca , Varesio Emmanuel , Staack Roland F. , Starke Volkmar , Richter Wolfgang F. , Hopfgartner Gérard
Published: May 2007

A qualitative and quantitative analysis of erlotinib (RO0508231) and its metabolites was carried out on rat tissue sections from liver, spleen and muscle. Following oral administration at a dose of 5 mg/kg, samples were analyzed by matrix‐assisted laser desorption ionization (MALDI) with mass spectrometry (MS) using an orthogonal quadrupole time‐of‐flight instrument. The parent compound was detected in all tissues analyzed. The metabolites following drug O‐dealkylation could also be detected in liver sections. Sinapinic acid (SA) matrix combined with the dried‐droplet method resulted in better conditions for our analysis on tissues. Drug quantitation was investigated by the standard addition method and liquid chromatography‐tandem mass spectrometry (LC‐MS/MS) analysis on the tissue extracts. The presence of the parent compound and of its O‐demethylated metabolites was confirmed in all tissue types and their absolute amounts calculated. In liver the intact drug was found to be 3.76 ng/mg tissue, while in spleen and muscle 6‐ and 30‐fold lower values, respectively, were estimated. These results were compared with drug quantitation obtained by whole‐body autoradiography, which was found to be similar. The potential for direct quantitation on tissue sections in the presence of an internal standard was also investigated using MALDI‐MS. The use of α‐cyano‐4‐hydroxycinnamic acid (CHCA) as the matrix resulted in better linearity for the calibration curves obtained with reference solutions of the drug when compared to SA, but on tissue samples no reliable quantitative analysis was possible owing to the large variability in the signal response. MS imaging experiments using MALDI in MS/MS mode allowed visualizing the distribution of the parent compound in liver and spleen tissues. By calculating the ratio between the total ion intensities of MS images for liver and spleen sections, a value of 6 : 1 was found, which is in good agreement with the quantitative data obtained by LC‐MS/MS analysis. Copyright © 2007 John Wiley & Sons, Ltd.
Effect of ENSO on Queensland seasonal landfalling tropical cyclone activity
Authors: Flay Shaun , Nott Jonathan
Published: May 2007

A statistical model for predicting seasonal tropical cyclone landfalls in Queensland, Australia using an index of the El Niño‐Southern Oscillation (ENSO) is presented. The approach uses a generalised linear model (GLM) to relate seasonal counts to the Southern Oscillation Index (SOI). A Bayesian methodology is employed to estimate parameters of the model. The available tropical cyclone record is first separated into historical (1910/1911–1959/1960) and instrumental (1960/1961–2004/2005) eras. Historical counts, which are considered to be less reliable observational sources, are used to specify informative prior distributions when fitting the GLM to instrumental counts with the Bayesian approach. The inclusion of historical information is found to lead to increased certainty in parameter estimates when compared to a model where historical counts are excluded and a non‐informative prior model used. Predictive distributions are given, which allow inferences on seasonal landfall activity, given pre‐seasonal values of the SOI. A cross‐validation procedure shows that the model incorporating historical information outperforms, in terms of mean‐squared prediction error, both the non‐informative prior model and a model without the SOI‐predictor (climatology). A trend analysis highlights possible decadal variability in the relationship between ENSO and seasonal tropical cyclone activity. Copyright © 2007 Royal Meteorological Society
Climate variability in Jordan
Authors: Freiwan Muwaffaq , Kadioǧlu Mikdat
Published: May 2007

Climate variability in Jordan is very sensitive to water resources, which are at the verge of depletion because annual per‐capita water is at one of the lowest levels in the world. In order to address such sensitivity, it is necessary to examine effective meteorological factors such as annual, seasonal and monthly precipitation and extreme (maximum and minimum) temperature time series. Fourteen representative meteorological stations are chosen for the study of climate variability calculations in Jordan. Annual and monthly time series of precipitation, maximum and minimum temperatures are tested by the runs (Swed–Eisenhart) homogeneity test. Consequently, the sequential version of the Mann–Kendall rank trend and the linear trend tests are applied to the interannual means, coefficient of variation and skewness parameters. Signals of climate trends such as warming in maximum temperature, more statistically significant warming in minimum temperature, decreasing trends in daily temperature range and statistically insignificant decreasing precipitation trends are detected, which are enhanced by heat island, urbanization, pollution and aerosols effects. Two spells are recognized in the time series, where the first spell started in the early 1970s and the second beyond the year 1992 with a warming trend in maximum temperature and a farther warming in minimum temperature resulting in a decreasing trend in the diurnal temperature range that is associated with a slight decrease in precipitation. The interannual coefficient of variation of maximum and minimum temperatures reveals increasing trends in the majority of the stations while they exhibit an apparent decreasing trend in diurnal temperature range and a general, but insignificant, decreasing trend in precipitation is observed. Copyright © 2007 Royal Meteorological Society
Cloud‐radiative impacts on the tropical Indian Ocean associated with the evolution of ‘monsoon breaks’
Authors: Samala Basanta Kumar , Krishnan R.
Published: May 2007

A detailed diagnostic analysis of a suite of observed datasets was carried out with a view to understand the importance of cloud‐radiative effects on the evolution of prolonged ‘monsoon breaks’ over the Indian region. The study particularly focuses on the role of clouds in affecting the sub‐seasonal/intra‐seasonal variability of sea surface temperature (SST) and atmospheric convection in the equatorial and south‐eastern tropical Indian Ocean (SETIO) during monsoon‐break transitions. A characteristic feature of the monsoon‐break evolution is the appearance of suppressed convection over the SETIO region nearly 7–10 days prior to the commencement of a break spell over India. It is seen from the present analysis that the lack of cloud cover over the SETIO during the ‘pre‐break’ phase leads to significant warming of the tropical Indian Ocean due to strong solar insolation at the surface. During the ‘pre‐break’ phase, the net cloud‐radiative forcing (NETCRF) at the surface is found to be typically around − 30 Wm−2 and the mean SST in the SETIO is about 29.3 °C. Following the transition to a monsoon‐break phase, the cloud amount increases by about 25% over the SETIO region in association with intensified convection. The NETCRF at the surface over the SETIO averaged during the ‘break’ phase is found to be about − 60 Wm−2 (i.e. a change of about − 30 Wm−2 from the ‘pre‐break’ phase). Consistent with the above change in the NETCRF, the SST in the SETIO shows a cooling of about 0.7 °C, although the mean SSTs during the ‘break’ phase remain as high as 28.6 °C. On the basis of the findings from this study, it is suggested that the SST warming during the ‘pre‐break’ phase plays a key role in maintaining high SST and allows sustained convection to occur over the SETIO during prolonged monsoon breaks. Copyright © 2007 Royal Meteorological Society
Weather regimes and sea surge variations over the Gulf of Lions (French Mediterranean coast) during the 20th century
Authors: Ullmann A. , Moron V.
Published: May 2007

Hourly sea surge variations observed at three tide‐gauge stations (Grau‐de‐la‐Dent(GD) located in the Rhône Delta, Sète(SE), and Port‐Vendres(PV)) around the Gulf of Lions are strongly correlated during the wintertime period (October to March) of 1986‐1995. Relationships between the early morning (6 a.m. UTC) sea surge observed at Grau‐de‐la‐Dent station and five weather regimes—Zonal (ZO), East‐Atlantic (EA), Greenland Above (GA), Blocking (BL), and Atlantic Ridge (AR)—over the northeast Atlantic and Europe (40°W–40°E, 30 –70°N) are analysed during the wintertime period of 1905‐2002. More than 75% of sea surges ≥ 40 cm occur during both of the weather regimes associated with a negative North Atlantic Oscillation(NAO) phase (41.2 and 34% during BL and GA weather regimes, respectively), ahead of low pressure travelling usually southeastward, on a stormtrack shifted south of 55°N. The relationships between monthly/seasonal frequency of weather regime and 75th percentile of sea surge at GD tend to strengthen during the 20th century: for example, correlation between seasonal frequencies of GA and 75th percentile of sea surge increases from 0.07 (not significant) in 1905–40 to 0.83 (signifiicant at the one‐sided 99% level) in 1974–2002. Copyright © 2007 Royal Meteorological Society
Spatial and temporal analysis of climatological data in Jordan
Authors: Freiwan Muwaffaq , Kadioglu Mikdat
Published: May 2007

This paper evaluates climate variability over Jordan by considering temporal and spatial variations on the basis of annual and seasonal meteorological variables including precipitation, relative humidity (RH), maximum and minimum temperatures over 30 years (1971–2000) at 16 representative observation stations over the whole country. The assessments are based on the statistical parameters such as the averages, coefficient of variation and skewness (SK). These parameters are mapped through the Kriging regional variability approach. Seasonal and annual parameter maps are presented and the climate variability interpretations are derived for the purpose of identifying climatologically homogenous precipitation regions. Climatic regions, temperature and humidity regimes, aridity and drought conditions in the country are determined, and the country is divided into three homogeneous precipitation regions. Copyright © 2007 Royal Meteorological Society
Andosols and soils with andic properties in the German soil taxonomy
Authors: Kleber Markus , Jahn Reinhold
Published: May 2007

The presence of soils with andic properties on German territory has been suspected for decades and there are numerous reports of sites where they may potentially occur. Andic properties, however, are not adequately represented by the German soil‐classification system. The German taxonomic category “Lockerbraunerde” has not been revised or reconciled with international taxonomic categories since the year 1957, when it was initially proposed. With this review, we show that there are true Andosols of both the silandic (allophane‐containing) and the aluandic (Al‐Humus‐dominated) type in Germany and that their properties differ substantially from other soils which merely exhibit low bulk density. By (1) comparing soil carbon storage between some German Andosols, Chernozems, and nonandic Cambisols with particularly low bulk density and (2) elucidation of the differential pedogenetic pathways leading to Andosol formation, we further demonstrate that Andosols are important objects of study in research issues of contemporary interest. We propose that appropriate measures be taken to lay the foundations for the protection and conservation of these soils, because they are valuable as archives of natural history and provide opportunities to study unique soil processes.
Impact of soil texture on temporal and spatial development of osmotic‐potential gradients between bulk soil and rhizosphere
Authors: Vetterlein Doris , Szegedi Krisztian , Stange Florian , Jahn Reinhold
Published: May 2007

Solute transport from the bulk soil to the root surface is, apart from changes in soil moisture and plant nutrient uptake, a prerequisite for changes in soil osmotic potential (Ψo). According to the convection‐diffusion equation, solute transport depends on a number of parameters (soil moisture–release curve, hydraulic conductivity, tortuosity factor) which are functions of soil texture. It was thus hypothesized that soil texture should have an effect on the formation of Ψo gradients between bulk soil and the root surface. The knowledge about such gradients is important to evaluate water availability in the soil‐plant‐atmosphere continuum (SPAC).

A linear compartment system with maize grown under controlled conditions in two texture treatments (T1, pure sand; T2, 80% sand, 20% silt) under low and high initial application of salts (S1, S2) was used to measure the development of Ψo gradients between bulk soil and the root surface by microscale soil‐solution sampling and TDR sensors.

The differences in soil texture had a strong impact on the formation of Ψo gradients between bulk soil and the root surface at high and low initial salt application rate. At high initial salt application, a maximum osmotic‐potential gradient (ΔΨo) of –340 kPa was observed for the texture treatment T2 compared to ΔΨo of –180 in T1. The steeper gradients in osmotic potential in treatment T2 compared to T1 corresponded to higher cumulative water consumption in this treatment which can partly be explained by higher soil hydraulic conductivity in the range of soil matric potentials covered during the duration of the experiments. Differences between texture treatments in Ψo at the root surface did not result in differences in plant‐water relations measured as gas‐exchange parameters (transpiration rate, water‐use efficiency) and leaf osmotic potential. If soil osmotic and matric potential are regarded as additive in calculating the driving force for water movement from the soil into the root, the observed differences in water flux between treatments cannot be explained.
Effect of nutrient‐management practices on growth, fruiting pattern, and yield of Asiatic cotton (Gossypium arboreum L.)
Authors: Blaise Desouza , Ravindran Chandragiri Dwarakanath , Singh Jag Vir
Published: May 2007

Asiatic cotton (Gossypium arboreum) is mostly grown in the rainfed regions of India. However, little is known about the effects of nutrient‐management practices on plant growth and fruiting pattern of Asiatic cotton. Therefore, plant growth and fruiting pattern under four nutrient‐management treatments, N, NPK, FYM (10 Mg ha–1), and INM (integrated nutrient management: a combination of NPK and FYM) were quantified during 2000–01 to 2002–03 (years 16 to 18 of a long‐term field experiment). Plants of the INM and FYM treatments were taller (68.4–149.5 cm) and had more main stem nodes per plant (30.5–44.5) as compared to N and NPK treatments. In treatment N, the shortest plants (50.9–83.6 cm) and the least number of fruiting structures were produced. Plants of the INM and FYM treatments accumulated more squares and bolls. Maximum boll production was 10–19 days earlier with the manure‐amended than the N and NPK treatments. Treatment N had the lowest seed cotton yield (639–790 kg ha–1), because of small boll size (1.48–1.73 g) and few open bolls. Seed cotton yield followed the trend: NPK (815–1278 kg ha–1) < INM (776–1551 kg ha–1) < FYM (902–1593 kg ha–1). Water stress and nutrient deficiencies (P and Zn in the N and Zn in the NPK treatments) as a consequence of nutrient depletion over the years may have decreased seed cotton yields in treatments that received mineral fertilizer alone in comparison with manure‐amended treatments. On a long‐term basis, FYM application should therefore form an integral part of nutrient recommendation.
Effects of throughfall and litterfall manipulation on concentrations of methylmercury and mercury in forest‐floor percolates
Authors: Hojdová Maria , Huang Jen‐How , Kalbitz Karsten , Matzner Egbert
Published: May 2007

The forest floor was shown to be an effective sink of atmospherically deposited methylmercury (MeHg) but less for total mercury (Hgtotal). We studied factors controlling the difference in dynamics of MeHg and Hgtotal in the forest floor by doubling the throughfall input and manipulating aboveground litter inputs (litter removal and doubling litter addition) in the snow‐free period in a Norway spruce forest in NE Bavaria, Germany, for 14 weeks. The MeHg concentrations in the forest‐floor percolates were not affected by any of the manipulation and ranged between 0.03 (Oa horizon) and 0.11 (Oi horizon) ng Hg L–1. The Hgtotal concentrations were largest in the Oa horizon (24 ng Hg L–1) and increased under double litterfall (statistically significant in the Oi horizon). Similarly, concentrations of dissolved organic C (DOC) increased after doubling of litterfall. The concentrations of Hgtotal and DOC correlated significantly in forest‐floor percolates from all plots. However, we did not find any effect of DOC on MeHg concentrations. The difference in the coupling of Hgtotal and MeHg to DOC might be one reason for the differences in the mobility of Hg species in forest floors with a lower mobility of MeHg not controlled by DOC.
Drought risk to agricultural land in Northeast and Central Germany
Authors: Schindler Uwe , Steidl Joerg , Müller Lothar , Eulenstein Frank , Thiere Jürgen
Published: May 2007

Aim of the study was the evaluation of the present state and further development of drought risk to agricultural sites in Northeast (NE) and Central Germany in consideration of climate changes. Based on the Medium Scale Agricultural Site Map, soil‐hydrological data were derived for heterogeneous soil areas. They refer to the landscapes in NE and Central Germany characterized by low precipitation, marked spatial soil heterogeneity, and a high share of hydromorphic soils. The soil data were linked with long‐term climate records of 368 stations for the period 1951–2000 as well as a climate scenario for the period 2001–2055. The plant water supply was calculated for three crop groups: cereals, root crops, and grass. The current and future development of drought risk of agricultural land of NE and Central Germany was evaluated. Starting in 1951, the water supply over the vegetation period has been decreasing with time for all crop groups up to now and may continue up to the year 2055 at most sites. However, there are also regions with increased plant water supply. The federal states of Brandenburg and Saxony‐Anhalt showed the strongest water deficit. Especially in these states, the plant water supply is strongly limited for cereals already today and probably may get worse for all crops in the future. On an average of the years, drought may limit plant growth in parts at >40% of agricultural land. In the federal states Mecklenburg‐Western Pomerania, Saxony, and Thuringia, the plant water supply mostly will stay in an approximately sufficient range due to higher precipitation and more favorable soil quality. The results are a background for the assessment of land‐use planning and evaluation of current and future soil‐ and site‐specific crop growing suitability on a medium scale.
Arbuscular mycorrhizal colonization and spore density across different land‐use types in a hot and arid ecosystem, Southwest China
Authors: Li Ling‐Fei , Zhang Yan , Zhao Zhi‐Wei
Published: May 2007

We investigated the arbuscular mycorrhizal (AM) colonization and spore density in cropped land, fallow land, and an undisturbed savanna ecosystem under hot and arid climatic conditions in a valley of southwest China. Plants surveyed in the three land‐use types showed heavy arbuscular mycorrhizal colonization, indicating a high mycorrhizal dependency of plants in this environment. One‐way analysis of variance (ANOVA) showed that the colonization of different AM structures and the spore density varied greatly among plant species both within and between different land‐use types. The AM colonization and spore density were higher in undisturbed than in fallow or cropped land. No significant correlation between AM colonization and spore density was observed when land‐use types were either considered separately or together. Cluster analysis based on the similarity in AM status with respect to both colonization and spore density showed similarities between fallow land and the undisturbed savanna. The results indicate that continuous cropping reduces AM colonization and spore density. These parameters appear to nearly fully recover when the land has been left to fallow for 4 years.