bluuebunny/crossref_metadata_2025 huggingface dataset:
Achiral plane trees
Authors: Wormald Nicholas
Published: May 2007

Harary and Robinson showed that the number an of achiral planted plane trees with n points coincides with the number pn of achiral plane trees with n points, for n ⩾ 2. They posed the problem of finding a natural structural correspondence which explains this coincidence. In the present paper this problem is answered by constructing two‐to‐one correspondences from certain sets of binary sequences to each of the sets of trees concerned, giving a structural basis for the equation 2an = 2pn. Answers are also supplied to similar correspondence‐type problems of Harary and Robinson, concerning planted plane trees, and achiral rooted plane trees. In addition, each of these four types of plane trees are counted with numbers of points and endpoints as the enumeration parameters. The results all show a symmetry with respect to the number of endpoints which is not shared by the set of all plane trees.
Long cycles in vertex‐transitive graphs
Authors: Babai László
Published: May 2007

We prove that every connected vertex‐transitive graph on n ≥ 4 vertices has a cycle longer than (3n)1/2. The correct order of magnitude of the longest cycle seems to be a very hard question.
Tournaments and Vandermond's determinant
Authors: Gessel Ira
Published: May 2007

We prove that det |xii–1|n × n = Π1≤i<i≤n (Xj – Xi) by associating a tournament to each term in the expansion of the product. All terms cancel except those corresponding to transitive tournaments, and their sum of the determinant.
On minimal 5‐chromatic triangle‐free graphs
Authors: Avis David
Published: May 2007

It is shown that the minimum number of vertices in a triangle‐free 5‐chromatic graph is at least 19.
On Whitney's 2‐isomorphism theorem for graphs
Authors: Truemper K.
Published: May 2007

Let G and H be 2‐connected 2‐isomorphic graphs with n nodes. Whitney's 2‐isomorphism theorem states that G may be transformed to a graph G* isomorphic to H by repeated application of a simple operation, which we will term “switching”. We present a proof of Whitney's theorem that is much shorter than the original one, using a graph decomposition by Tutte. The proof also establishes a surprisingly small upper bound, namely n‐2, on the minimal number of switchings required to derive G* from G. The bound is sharp in the sense that for any integer N there exist graphs G and H with n ≥ N nodes for which the minimal number of switchings is n‐2.
Extremal maximal uniquely hamiltonian graphs
Authors: Barefoot Curtiss A. , Entringer R. C.
Published: May 2007

Let G be a graph of order n with exactly one Hamiltonian cycle and suppose that G is maximal with respect to this property. We determine the minimum number of edges G can have.
Subgraphs smaller than the girth
Authors: Simoncini Luca , Taylor Herbert
Published: May 2007

For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k‐node tree T, then for every k‐node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.
Note on a new coloring number of a graph
Authors: Horák P. , Širáň J.
Published: May 2007

The distance coloring number Xd(G) of a graph G is the minimum number n such that every vertex of G can be assigned a natural number m ≤ n and no two vertices at distance i are both assigned i. It is proved that for any natural number n there exists a graph G with Xd(G) = n.
On the crossing numbers of products of cycles and graphs of order four
Authors: Beineke Lowell W. , Ringeisen Richard D.
Published: May 2007

The main results are that the crossing number of the product C4 × Cn is 2n for n ≥ 4 and that of the product K4 × Cn is 3n for n ≥ 3. These are extensions of an earlier result giving the crossing number of C3 × Cn as n for n ≥ 3.
A determination of the toroidal k‐metacyclic groups
Authors: Gross Jonathan L. , Lomonaco Samuel J.
Published: May 2007

Kronecker studied a class of groups 〈p, p ‐ 1, r〉, whose commutator subgroups are prime cyclic of order p, and whose commutator quotient groups are cyclic of order p ‐ 1. These are now commonly called the K‐metacyclic groups. It follows from the classical work of Maschke that none of the K‐metacyclic groups except 〈3, 2, 2〉 has a planar Cayley graph. It is proved here that only for p = 5 and p = 7 is a K‐metacyclic group 〈p, p ‐ 1, r〉 toroidal. To achieve this result, this paper develops a methodology for using Proulx's classification of toroidal groups by presentation to determine whether an explicitly given group is toroidal.
A note on generalized line graphs
Authors: Cameron Peter J.
Published: May 2007

Whitney's theorem on line graphs is extended to the class of generalized line graphs defined by Hoffman.
Two sets of graceful graphs
Authors: Delorme Charles
Published: May 2007

We give graceful numberings to the following graphs: (a) the union of n K4 having one edge in common, in other words the join of K2 and the union of n disjoint K2 and (b) the union of n C4 having one edge in common, in other words the product of K2 and K1,n, with n + 1 not a multiple of 4.
On a conjecture on maximal planar sequences
Authors: Fanelli Stefano
Published: May 2007

Let d1 d2 dp denote the nonincreasing sequence d1, …, d1, d2, …, d2, …, dp, …, dp, where the term di appears ki times (i = 1, 2, …, p). In this work the author proves that the maximal 2‐sequences: 7361515, 7561517, 7761519 are planar graphical, in contrast to a conjecture by Schmeichel and Hakimi.
Hypotraceable digraphs
Authors: Grötschel Martin , Thomassen Carsten , Wakabayashi Yoshiko
Published: May 2007

A hypotraceable digraph is a digraph D = (V, E) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which D ‐ v is traceable for all ve ∈ V. We prove that a hypotraceable digraph of order n exists iff n ≥ 7 and that for each k ≥ 3 there are infinitely many hypotraceable oriented graphs with a source and a sink and precisely k strong components. We also show that there are strongly connected hypotraceable oriented graphs and that there are hypotraceable digraphs with precisely two strong components one of which is a source or a sink. Finally, we prove that hypo‐Hamiltonian and hypotraceable digraphs may contain large complete subdigraphs.
Medians of arbitrary graphs
Authors: Slater Peter J.
Published: May 2007

For each vertex u in a connected graph H, the distance of u is the sum of the distances from u to each of the vertices v of H. A vertex of minimum distance in H is called a median vertex. It is shown that for any graph G there exists a graph H for which the subgraph of H induced by the median vertices is isomorphic to G.
On the number of cycles of length 4 in a maximal planar graph
Authors: Alameddine Ahmad Fawzi
Published: May 2007

Let p and C4 (G) be the number of vertices and the number of 4‐cycles of a maximal planar graph G, respectively. Hakimi and Schmeichel characterized those graphs G for which C4 (G) = 1/2(p2 + 3p ‐ 22). This characterization is correct if p ≥ 9. However, for p = 7 or 8, there is exactly one other graph which violates the theorem in the sense that the upper bound of C4 (G) is also attained.
A note on conservative graphs
Authors: White Arthur T.
Published: May 2007

An application of conservative graphs to topological graph theory is indicated.
On the existence of generalized good and equitable edge colorings
Authors: De Werra D.
Published: May 2007

Some classes of graphs are described which are extensions of bipartite multigraphs. Exclusion of some specific partial subgraphs gives some properties of edge colorability. in particular sufficient conditions are developed for the existence of generalized good and equitable colorings.
On the edge‐coloring problem for a class of 4‐regular maps
Authors: Jaeger F. , Shank H.
Published: May 2007

A (plane) 4‐regular map G is called C‐simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ (G) is the smallest integer k such that the curves of G can be colored with k colors in such a way that no two curves of the same color intersect. We prove that if σ (G) ≤ 4, G is edge colorable with 4 colors. Moreover we show that a similar result for maps G with σ(G) ≤ 5 would imply the Four‐Color Theorem.
Some results on the genus of a group
Authors: Tucker Thomas W.
Published: May 2007

This Note announces two results on the genus of a group. First, there is exactly one group of genus two, thus answering a question of V. K. Proulx. Second, the genus of the full symmetric group of degree n is n!/168 + 1, for all n > 167.
Quadrilateral embeddings of bipartite graphs
Authors: Anderson Ian
Published: May 2007

Current graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions of Kn and Kn, n into graphs with quadrilateral embeddings are discussed, and some thickness results are obtained. Some new genus results are also obtained.
On graphs containing a given graph as center
Authors: Buckley Fred , Miller Zevi , Slater Peter J.
Published: May 2007

We examine the problem of embedding a graph H as the center of a supergraph G, and we consider what properties one can restrict G to have. Letting A(H) denote the smallest difference ∣V(G)∣ ‐ ∣V(H)∣ over graphs G having center isomorphic to H it is demonstrated that A(H) ≤ 4 for all H, and for 0 ≤ i ≤ 4 we characterize the class of trees T with A(T) = i. for n ≥ 2 and any graph H, we demonstrate a graph G with point and edge connectivity equal to n, with chromatic number X(G) = n + X(H), and whose center is isomorphic to H. Finally, if ∣V(H)∣ ≥ 9 and k ≥ ∣V(H)∣ + 1, then for n sufficiently large (with n even when k is odd) we can construct a k‐regular graph on n vertices whose center is isomorphic to H.
On Graphs Without Multicliqual Edges
Authors: Chong‐Keang Lim , Yee‐Hock Peng
Published: May 2007

An edge which belongs to more than one clique of a given graph is called a multicliqual edge. We find a necessary and sufficient condition for a graph H to be the clique graph of some graph G without multicliqual edges. We also give a characterization of graphs without multicliqual edges that have a unique critical generator. Finally, it is shown that there are infinitely many self‐clique graphs having more than one critical generator.
Cages—a survey
Authors: Wong Pak‐Ken
Published: May 2007

We discuss the problem of finding smallest graphs of given girth g and valency v ((v, g)‐cages). All known (v, g)‐cages are given. Different variations of the cage problem are also discussed.
Exceptional trivalent cayley graphs for dihedral groups
Authors: Powers David L.
Published: May 2007

If n is divisible by at least three distinct primes, the dihedral group Dn can be generated by three nonredundant, involuntary elements. We study the Cayley graphs resulting from such a presentation of Dn for several families of n and for all admissible n < 120. All these graphs are trivalent, bipartite, Hamiltonian, of girth 6, and are regular representations of their groups. For each n, the isomorphism classes are determined and the graphs are described by a simple code.
On one‐factorizations of compositions of graphs
Authors: Himelwright P. , Wallis W. D. , Williamson J. E.
Published: May 2007

Let G[H] denote the composition of the graphs G and H. If G can be decomposed into one‐factors and two‐factors, H can be decomposed into one‐factors, and H is not the empty graph on an odd number of vertices, then G[H] can be decomposed into one‐factors.
On digraphs without antidirected cycles
Authors: Grant Douglas D. , Jaeger F. , Payan C.
Published: May 2007

Let t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n − 1)] ≤ t(n) ≤ 1/2 (n − 1) for n ≥ 5. Let tr (n) denote the corresponding quantity for r‐colorable digraphs. We show that [16/5(n − 1)] ≤ t5(n) ≤ t6(n) ≤ 10/3(n − 1) for n ≥ 5 and that t4(n) = 3(n − 1) for n ≥ 3.
On a conjecture of bollobás and bosák
Authors: Znám Štefan
Published: May 2007

It is shown that, for all sufficiently large k, the complete graph Kn can be decomposed into k factors of diameter 2 if and only if n ≥ 6k.
Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable
Authors: Thomason Andrew
Published: May 2007

The generalized Petersen graph P(6k + 3, 2) has exactly 3 Hamiltonian cycles for k ≥ 0, but for k ≥ 2 is not uniquely edge colorable. This disproves a conjecture of Greenwell and Kronk [1].
The bandwidth problem for graphs and matrices—a survey
Authors: Chinn P. Z. , Chvátalová J. , Dewdney A. K. , Gibbs N. E.
Published: May 2007

The bandwidth problem for a graph G is to label its n vertices vi with distinct integers f(vi) so that the quantity max{| f(vi) − f(vi)| : (vi vj) ∈ E(G)} is minimized. The corresponding problem for a real symmetric matrix M is to find a symmetric permutation M' of M so that the quantity max{| i − j| : m'ij ≠ 0} is minimized. This survey describes all the results known to the authors as of approximately August 1981. These results include the effect on bandwidth of local operations such as refinement and contraction of graphs, bounds on bandwidth in terms of other graph invariants, the bandwidth of special classes of graphs, and approximate bandwidth algorithms for graphs and matrices. The survey concludes with a brief discussion of some problems related to bandwidth.
Distribution of points by degree and orbit size in a large random tree
Authors: Bailey C. K.
Published: May 2007

Using generating functions and asymptotic techniques, the probability that in a large random tree a point is of degree r and an orbit of size s for r ≤ 7 and s ≤ 7 is calculated. For example, it is found that about 17% of the points of a random tree are fixed and have degree one. This method is readily applied to different types of trees.
The maximum number of arc‐disjoint arborescences in a tournament
Authors: Chung‐fan Ma , Mao‐cheng Cai
Published: May 2007

In this article, we give the maximum number of arc‐disjoint arborescences in a tournament or an oriented complete r‐partite graph by means of the indegrees of its vertices.
Orientations of circle graphs
Authors: Read R. C. , Rotem D. , Urrutia J.
Published: May 2007

Let C(v1, …,vn) be a system consisting of a circle C with chords v1, …,vn on it having different endpoints. Define a graph G having vertex set V(G) = {v1, …,vn} and for which vertices vi and vj are adjacent in G if the chords vi and vj intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v1, …,vn) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v1, …,vn) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.
Bipartite graphs with cycles of all even lengths
Authors: Schmeichel Edward , Mitchem John
Published: May 2007

Let G = (X, Y, E) be a bipartite graph with X = Y = n. Chvátal gave a condition on the vertex degrees of X and Y which implies that G contains a Hamiltonian cycle. It is proved here that this condition also implies that G contains cycles of every even length when n > 3.
A sufficient condition for a graph to contain three disjoint 1‐factors
Authors: Win Sein
Published: May 2007

Ore derived a sufficient condition for a graph to contain a Hamiltonian cycle. We obtain a sufficient condition, similar to Ore's condition, for a graph to contain a Hamiltonian cycle and a 1‐factor which are edge disjoint.
A survey of bounds for classical Ramsey numbers
Authors: Chung F. R. K. , Grinstead C. M.
Published: May 2007

This paper is a survey of the methods used for determining exact values and bounds for the classical Ramsey numbers in the case that the sets being colored are two‐element sets. Results concerning the asymptotic behavior of the Ramsey functions R(k,l) and Rm(k) are also given.
Size Ramsey numbers for small‐order graphs
Authors: Faudree R. J. , Sheehan J.
Published: May 2007

A table of the size Ramsey number or the restricted size Ramsey number for all pairs of graphs with at most four vertices and no isolated vertices is given.
Ramsey theory for graph connectivity
Authors: Matula David W.
Published: May 2007

rc(k) Denotes the smallest integer such that any c‐edge‐coloring of the rc(k) vertex complete graph has a monochromatic k‐connected subgraph. For any c, k ≧ 2, we show 2c(k – 1) + 1 ≦ rc(k) < 10/3 c(k – 1) + 1, and further that 4(k – 1) + 1 ≧ r2(k) < (3 + √ (k – 1) + 1. Some exact values for various Ramsey connectivity numbers are also computed.
A theorem on paths in planar graphs
Authors: Thomassen Carsten
Published: May 2007

We prove a theorem on paths with prescribed ends in a planar graph which extends Tutte's theorem on cycles in planar graphs [9] and implies the conjecture of Plummer [5] asserting that every 4‐connected planar graph is Hamiltonian‐connected.
On sequential labelings of graphs
Authors: Grace Thom
Published: May 2007

A valuation on a simple graph G is an assignment of labels to the vertices of G which induces an assignment of labels to the edges of G. β‐valuations, also called graceful labelings, and α‐valuations, a subclass of graceful labelings, have an extensive literature; harmonious labelings have been introduced recently by Graham and Sloane. This paper introduces sequential labelings, a subclass of harmonious labelings, and shows that any tree admitting an α‐valuation also admits a sequential labeling and hence is harmonious. Constructions are given for new families of graceful and sequential graphs, generalizing some earlier results. Finally, a conjecture of Frucht is shown to be wrong by exhibiting several graceful labelings of wheels in which the center label is larger than previously thought possible.
The number of connected sparsely edged graphs. IV large nonseparable graphs
Authors: Wright E. M.
Published: May 2007

The number of nonseparable graphs on n labeled points and q lines is u(n, q). In the second paper of this series an exact formula for u(n, n + k) was found for general n and successive (small) k. The method would give an asymptotic approximation for fixed k as n → ∞. Here an asymptotic approximation to u(n, n + k) is found when k = O(n1/2) and an approximation to logu(n, n + k) when k < (1 ‐ ϵ)(1/3 n)1/2. The problem of finding an approximation to u(n, q) when (q ‐ n)/n1/2 → + → and q/n ‐ 1/2 logn ‐ 1/2 log logn → ‐ ∞ is open.
Integer flows
Authors: Younger D. H.
Published: May 2007

A k‐flow is an assignment of edge directions and integer weights in the range 1, …., k – 1 to the edges of an undirected graph so that ateach vertex the flow in is equal to the flow out. This paper gives a polynomial algorithm for finding a 6‐flow that applies uniformly to each graph. The algorithm specializes to give a 5‐flow for planar graphs.
On a product dimension of bipartite graphs
Authors: Poljak S. , Rödl D. , Pultr A.
Published: May 2007

A product dimension of bipartite graphs bid G analogous to the Dushnik‐Miller dimension of posets and to the dimension of general symmetric graphs is studied. It is shown that bidG ≦ 1/2|V(G)| + 1 and almost all bipartite graphs G have bidG close to 1/2|V(G)|. On the other hand it is shown to be considerably less for everyday graphs like trees, cycles, cubes, etc.
On the sum of all distances in a graph or digraph
Authors: Plesník Ján
Published: May 2007

The transmission of a graph or digraph G is the sum of all distances in G. Strict bounds on the transmission are collected and extended for several classes of graphs and digraphs. For example, in the class of 2‐connected or 2‐edge‐connected graphs of order n, the maximal transmission is realized only by the cycle Cn. The independence of the transmission on the diameter or radius is shown. Remarks are also given about the NP‐hardness of some related algorithmic problems.
Subdivisions of graphs with large minimum degree
Authors: Thomassen Carsten
Published: May 2007

We prove a theorem on path systems implying the conjecture of Bollobás that there exists a function f(k, m) (where k and m are natural numbers) satisfying the following: For each graph G of minimum degree at least f(k, m) there exists a graph H of minimum degree at least k such that G contains the graph obtained from H by subdividing each edge m times.
Recognizing decomposable graphs
Authors: Chvátal V.
Published: May 2007

A graph is called decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We point out a simple and efficient algorithm for recognizing decomposable graphs with maximum degree at most 3 and prove that recognizing decomposable graphs with maximum degree 4 is an NP‐complete problem.
Factors and factorizations of graphs—a survey
Authors: Akiyama Jin , Kano Mikio
Published: May 2007

A degree factor of a graph is either an r‐factor (regular of degree r) or an [m, n]‐factor (with each degree between m and n). In a component factor, each component is a prescribed graph. Both kinds of factors are surveyed, and also corresponding factorizations.
Almost‐regular factorization of graphs
Authors: Akiyama Jin , Kano Mikio
Published: May 2007

For integers a and b, 0 ⩽ a ⩽ a ⩽ b, an [a, b]‐graph G satisties a ⩽ deg(x, G) ⩽ b for every vertex x of G, and an [a, b]‐factor is a spanning subgraph F such that a ⩽ deg(x, F) ⩽ b for every vertex x of F. An [a, b]‐factor is almost‐regular if b = a + 1. A graph is [a, b]‐factorable if its edges can be decomposed into [a, b]‐factors. When both K and t are positive integers and s is a nonnegative integer, we prove that every [(12K + 2)t + 2ks, (12k + 4)t + 2ks]‐graph is [2k,2k + 1]‐factorable. As its corollary, we prove that every [r.r + 1]‐graph with r ⩾ 12k2 + 2k is [2k + 1]‐factorable, which is a partial extension of the two results, one by Thomassen and the other by Era.
Almost reconstructing infinite, rayless graphs
Authors: Schmidt Rüdiger
Published: May 2007

We show that for every infinite, rayless graph G the following holds. If G is hypomorphic to H then G is isomorphic to an induced subgraph of G. This proves a conjecture of R. Halin for the class of infinite, rayless graphs and partly extends a result of Bondy and Hemminger. The proof makes use of the structure theory for rayless graphs which was developed by the author in a previous paper.
Extremal graphs of diameter at most 6 after deleting any vertex
Authors: Usami Yoko
Published: May 2007

Suppose G is a graph of n vertices and diameter at most d having the property that, after deleting any vertex, the resulting subgraph has diameter at most 6. Then G contains at least max{n, (4n ‐ 8)/3} edges if 4 ≤ d ≤ 6.
Large bipartite graphs with given degree and diameter
Authors: Delorme C.
Published: May 2007

We give constructions of bipartite graphs with maximum Δ, diameter D on B vertices, such that for every D ≥ 2 the lim infΔ→∞B. Δ1‐D = bD > 0. We also improve similar results on ordinary graphs, for example, we prove that limΔ→∞N · Δ−D = 1 if D is 3 or 5. This is a partial answer to a problem of Bollobás.
On self‐complementation
Authors: Benhocine A. , Wojda A. P.
Published: May 2007

We prove that, with very few exceptions, every graph of order n, n − 0, 1(mod 4) and size at most n − 1, is contained in a self‐complementary graph of order n. We study a similar problem for digraphs.
Arc transitive covering digraphs and their eigenvalues
Authors: Babai L.
Published: May 2007

We prove that every finite regular digraph has an arc‐transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2‐arc‐transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex‐transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc‐transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc‐transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2‐arc‐transitive graphs X.
Lengths of cycles in halin graphs
Authors: Bondy J. A. , Lovász L.
Published: May 2007

A Halin graph is a plane graph H = T U C, where T is a plane tree with no vertex of degree two and at least one vertex of degree three or more, and C is a cycle connecting the endvertices of T in the cyclic order determined by the embedding of T. We prove that such a graph on n vertices contains cycles of all lengths l, 3 ≤ l n, except, possibly, for one even value m of l. We prove also that if the tree T contains no vertex of degree three then G is pancyclic.
The graph reconstruction number
Authors: Harary Frank , Plantholt Michael
Published: May 2007

The reconstruction number of graph G is the minimum number of point‐deleted subgraphs required in order to uniquely identify the original graph G. We list, based on computer calculations, the reconstruction number for all graphs with at most seven points. Some constructions and conjectures for graphs of higher order are given. the most striking statement is our concluding conjeture that almost all graphs have have reconstruction number three.
Classes of interval graphs under expanding length restrictions
Authors: Fishburn P. C. , Graham R. L.
Published: May 2007

Let C(α) denote the finite interval graphs representable as intersection graphs of closed real intervals with lengths in [1, α]. The points of increase for C are the rational α ≥ 1. The set D(α) = [∩β>αC(β)]\C(α) of graphs that appear as soon as we go past α is characterized up to isomorphism on the basis of finite sets E(α) of irreducible graphs for each rational α. With α = p/q and p and q relatively prime, ∣E(α)∣ is computed for all (p,q) with q ⩽ 2 and p = q + 1. When q = 1, E(p) contains only the bipartite star K1, p+2. A lowr bound on ∣E(α)∣ is given for all rational α.
Some conditions for the existence of f‐factors
Authors: Katerinis P.
Published: May 2007

Let m, l, n be three odd integers such that m > l > n. It is proved that if a graph G has an m‐factor and an n‐factor, then it also has an l‐factor. In addition, we obtain sufficient conditions for the existence of an f‐factor, in terms of vertex‐deleted subgraphs.
Connectivity of circulant digraphs
Authors: Van Doorn Erik A.
Published: May 2007

An explicit expression is derived for the connectivity of circulant digraphs.
Bijective proofs of two broken circuit theorems
Authors: Blass Andreas , Sagan Bruce Eli
Published: May 2007

We prove, by means of explicit bijections, theorems of Whitney and Stanley that express the coefficients of the chromatic polynomial of a graph G and the number of acyclic orientations of G in terms of numbers of sets of edges that contain no broken circuits of G.
One‐legged caterpillars span hypercubes
Authors: Havel I. , Liebl P.
Published: May 2007

The aim of this paper is to prove that any balanced caterpillar having 2n vertices and maximum degree 3 spans the n‐dimensional hypercube.
Minimum k‐hamiltonian graphs, II
Authors: Paoli M. , Wong W. W. , Wong C. K.
Published: May 2007

We consider in this paper graphs which remain hamiltonian after the removal of k edges (k‐edge hamiltonian) or k vertices (k‐hamiltonian). These classes of graphs arise from reliability considerations in network design. In a previous paper, W. W. Wong and C. K. Wong presented families of minimum k‐hamiltonian graphs and minimum k‐edge hamiltonian graphs for k even. Here, we complete this study in the case where k is odd.
On the domination of the products of graphs II: Trees
Authors: Jacobson Michael S. , Kinch Lael F.
Published: May 2007

For a graph G, a subset of vertices D is a dominating set if for each vertex X not in D, X is adjacent to at least one vertex of D. The domination number, γ(G), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H,

One result presented in this paper settles this question in the case when at least one of G or H is a tree. We show that

for all graphs G and any tree T.

Furthermore, we supply a partial characterization for which pairs of trees, T1 and T2, strict inequality occurs. We show

for almost all pairs of trees.
Parity theorems for paths and cycles in graphs
Authors: Bondy J. A. , Halberstam F. Y.
Published: May 2007

We extend an elegant proof technique of A. G. Thomason, and deduce several parity theorems for paths and cycles in graphs. For example, a graph in which each vertex is of even degree has an even number of paths if and only if it is of even order, and a graph in which each vertex is of odd degree has an even number of paths if and only if its order is a multiple of four. Our results have implications for generalized friendship graphs and their conjectured nonexistence.
The six bidecomposable graphs
Authors: Ando Kiyoshi , Mizuno Hirobumi
Published: May 2007

A graph G is said to be decomposable if G can be decomposed into a cartesian product of two nontrivial graphs. G is bidecomposable if not only G but also its complement G is decomposable. We prove that there are only six bidecomposable graphs; 2K(2), C4, Q3, K(2) ×(K(2) + K(2)), K(3) × K(3).
Linear arboricity for graphs with multiple edges
Authors: Aït‐djafer Houria
Published: May 2007

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ(G), the linear arboricity la(G) satisfies ⌈Δ(G)/2⌉ ≦ la(G) ≦ ⌈(Δ(G) + 1)/2⌉. Here it is proved that if G is a loopless graph with maximum degree Δ(G) ≦ k and maximum edge multiplicity μ(G) ≦ k − 2n+1 + 1, where k ≧ 2n−2, then la(G) ≦ k − 2n. It is also conjectured that for any loopless graph G, ⌈Δ(G)/2⌉ ≦ la(G) ≦ ⌈(Δ(G) + μ(G))/2⌉.
Laser desorption/ionization techniques in the characterization of high‐molecular‐weight oil fractions—Part 2: de‐asphalted oils
Authors: Rizzi Andrea , Cosmina Paola , Flego Cristina , Montanari Luciano , Smaniotto Anna , Seraglia Roberta , Traldi Pietro
Published: May 2007

The composition of the de‐asphalted oil fraction obtained from two different Italian fields was studied by laser desorption/ionization mass spectrometry. These fractions were treated with different solvent mixtures, and subfractions containing saturates, aromatic and polar compounds were obtained and analyzed by the same instrumental approach.

The investigation showed clear differences between the samples coming from the two oils. The instrumental approach did not lead to an accurate description of the different components in terms of elemental composition and structures; however, valid information could be obtained on the molecular weight distribution of the components of the different fractions. Copyright © 2007 John Wiley & Sons, Ltd.
Long lead rainfall forecasts for the Australian sugar industry
Authors: Everingham Y. L. , Clarke A. J. , Van Gorder S.
Published: May 2007

Rainfall variability is a crucial element that impinges on the success of sugarcane growing regions around the world. As the scientific community and industry personnel gain more experience at working participatively, the ability of long‐range rainfall forecasts to reduce the risk and uncertainty associated with decisions impacted by rainfall variability has become increasingly recognized. Some important decisions, however, require knowing the chances of rain at early lead times that span the austral autumn period. These types of decisions remain largely unassisted by climate forecasting technologies owing to the boreal spring (austral autumn) persistence barrier. Taking the Australian sugar industry as a case study example, this article explores the capability of a long lead statistical El Niño Southern Oscillation phenomenon (ENSO) prediction model to reduce the risk associated with decisions that must be made before autumn and are effected by rainfall anomalies post‐autumn. Results shown across all regions considered in this study indicated a higher risk of obtaining an above‐median rainfall index when the statistical model predicted La Niña type conditions to emerge post‐spring. For selected regions, this risk was reduced when the model predicted El Niño type conditions for the same period. In addition, the model would have provided an earlier indication of the likelihood of disruption due to wet harvest conditions in a year that devastated the Australian sugar industry. This benchmark study has highlighted the potential of an ENSO prediction model to aid industry decisions that have previously been made in isolation of probabilistic knowledge about future rainfall conditions. Copyright © 2007 Royal Meteorological Society
Historical trends and future predictions of climate variability in the Brahmaputra basin
Authors: Immerzeel Walter
Published: May 2007

An innovative approach is developed and presented to assess historical climate variations and to quantify future climate change for the entire Brahmaputra basin. Historical trends in temperature and precipitation are analysed from 1900 to 2002 for the Tibetan plateau (TP), the Himalayan belt and the floodplains (FP) using a global 100 year monthly high resolution dataset. Temperature patterns are consistent with global warming and out of the 10% warmest years from 1900 to 2002 six occurred between 1995 and 2002. No clear trends in precipitation were found and annual precipitation in the basin is mainly determined by the strength of the monsoon. Regression analysis is used to further explain monsoon precipitation. A significant inverse relation is found between air temperature differences between the FP and the TP and the strength of the monsoon, whereas the El Niño Southern Oscillation teleconnection does not have a prominent role in explaining variation in monsoon precipitation. Simulation results of six general circulation models are statistically downscaled to the spatial resolution of the observed dataset for two future storylines. The analysis predicts accelerated seasonal increases in both temperature and precipitation from 2000 to 2100. The largest changes occur on the TP and the smallest on the FP. Multiple regression analysis shows a sharp increase in the occurrence of average and extreme downstream discharges for both storylines. The strongest increases are projected for the monsoon season and the largest threat of climate change lies in the associated flooding in the densely populated FP. Copyright © 2007 Royal Meteorological Society
Quantification of soil structural changes induced by cereal anchorage failure: Image analysis of thin sections
Authors: J. Mooney Sacha , Morris Catherine , Craigon James , Berry Peter
Published: May 2007

Cereal anchorage failure, or lodging, is the permanent displacement of a crop from the vertical and results in significant annual yield losses globally. Several factors have been identified as contributors to this phenomenon but the precise mechanisms of failure are still largely unknown because of difficulties in observing these processes as they occur in situ. To identify potential soil management practices to minimize losses associated with cereal root failure, an understanding of the nature of root‐soil interactions attributed to lodging is needed. An experiment was conducted that involved field impregnation and subsequent thin sectioning of lodged and unlodged root‐soil complexes from contrasting soils, cereal crops, and management practices to elucidate the effects of lodging on soil structure and porous architecture. Using image analysis, size and distribution of pores in soils were quantified at both meso‐ (100–30 μm) and microscales (<30 μm). A significant effect of lodging on porosity was recorded whereby lodging reduced total porosity through compaction created by movement of the stem base, although this was variable among soil types. Pore‐size distributions comprehensively supported these trends since alteration in the relative frequency of pores within specific size classes was clearly observed. The effects of lodging were more pronounced at the mesoscale because the data were more susceptible to variations created by natural soil heterogeneity at the microscale. These data suggested that sideways movement of the subterranean stem within the soil is a significant factor which is likely to affect the propensity for a cereal plant to lodge, indicating soil strength in the upper part of the soil profile is crucial.
Measurement of dew, fog, and rime with a high‐precision gravitation lysimeter
Authors: Meissner Ralph , Seeger Juliane , Rupp Holger , Seyfarth Manfred , Borg Heinz
Published: May 2007

Exact information about soil water flow is needed to quantify solute transfer within the unsaturated zone. Water flux densities are often measured indirectly, e.g., with water‐balance, water content–change, or tracer methods, and, therefore, often predicted with notable uncertainties. Over the last years, direct lysimetry methods have been increasingly used to study water and solute migration in soil profiles. A large weighable lysimeter is the best method to obtain reliable drainage data, but it requires relatively high investment and maintenance expenses. To reduce cost and improve comparability with undisturbed sites, a new technology to collect large monolithic soil columns with a surface area of 0.5–2 m2 and a depth of 1–3 m as well as a containerized polyethylene (PE‐HD) lysimeter station were developed. In addition, the station was fitted with a new high‐precision weighing technique. In this paper, the latter is demonstrated with data from a newly constructed gravitation lysimeter. Besides recording rainfall and seepage, its weighing precision makes it possible to register mass input by dew, fog, or rime. It also permits a very accurate calculation of actual evapotranspiration. Because this new type of lysimeter allows a very high temporal resolution, it is ideally suited to develop and test models for soil hydrologic processes.
Copper, zinc, and cadmium accumulation in two prairie soils and crops as influenced by repeated applications of manure
Authors: Lipoth Sarah L. , Schoenau Jeffrey J.
Published: May 2007

A study was conducted to determine the effect of repeated (5–7 y) annual application of liquid swine or solid cattle manure on the plant availability of copper (Cu), zinc (Zn), and cadmium (Cd) at two field sites in the W‐central and E‐central agricultural regions of Saskatchewan, Canada. Soil samples, plant‐straw and grain samples from the 2003 growing season were collected and analyzed for total Cu, Zn, and Cd concentrations using nitric acid microwave digestion followed by atomic‐absorption spectroscopy. An ammonium bicarbonate diethylenetriaminepentaacetic acid (AB‐DTPA) extraction was performed on the soil samples as a measure of the plant‐available fraction. Crop plants that were tested included wheat (Triticum aestivum L.) and barley (Hordeum vulgare L.). The results of this study indicated that long‐term repeated applications of manure fertilizer sometimes resulted in increased plant availability of Cu, Zn, and Cd, as reflected in increased concentrations of the plant‐available metal observed both in the soil and plant tissue. In the case of Cu and Zn, these increases were related to the rate of application, as the manure is a source of Cu and Zn. Changes in soil conditions from repeated manure application, including a decrease in pH and stimulated plant‐root growth can explain the effect that both manure and urea‐fertilizer application had on increasing the Cd concentration in the plant. Overall, there does not appear to be any concern about soil metal loading and plant accumulation in these soils after 5–7 y of manure application, as soil and plant concentrations were well below the allowable limits.
Contribution of mineral nutrition to the response of barley seedlings to polyethylene glycol–induced mild water stress
Authors: Kocheva Konstantina V. , Georgiev Georgi I. , Vunkova‐Radeva Reneta V.
Published: May 2007

The effect of polyethylene glycol–induced osmotic stress on the activity of nitrate reductase, glutamine synthetase, and glycolate oxidase in leaves of young barley plants grown under two nutrient‐supply regimes was studied. The activity of nitrate reductase gradually decreased after polyethylene glycol (PEG) application, while glutamine synthetase and glycolate oxidase were increased. It is speculated that the enhanced glutamine synthetase and glycolate oxidase activities are due to increased flux of metabolites through the photorespiratory cycle. Prominent increase in concentrations of free proline, reducing sugars, and free amino acids was observed. The possible contribution of these cellular solutes to the process of osmotic adjustment and the role of mineral supply is discussed. It is suggested that low N supply in combination with stress conditions switched the preferred osmolyte type from amino acids (N‐containing) to sugars (C‐containing).
The pH effects on the growth rate of KDP (KH2PO4) crystal by investigating Raman active lattice modes
Authors: Badrouj M. , Malekfar R.
Published: May 2007

We report on the dependence of the pH value on the growth rates of KDP single crystals. Extensive experimental work has been carried out in order to find the optimum pH ranges for growing KDP single crystals with suitable sizes and high optical quality. Different techniques including micro‐Raman back‐scattering spectroscopy, UV/vis/IR transmission spectroscopy and X‐ray diffraction have been employed for this investigation. Deuterated substituted single crystals of KDP and DKDP also have been grown for the investigation of growth rates and Raman active mode identification purposes. The molecular vibration modes of the grown crystals, including internal modes of PO4 tetrahedrons molecular vibrations, external modes of optical phonons and hydrogen bonding modes have been determined exactly by micro‐Raman back‐scattering spectroscopy. The best pH values of the solution for the KDP crystal growth with reasonably higher growth rates from aqueous solutions that have been supersaturated ata temperature range of 30–50 °C have been found to be in the pH range of 3.2–5.4. Copyright © 2007 John Wiley & Sons, Ltd.
Purification and characterization of pectin methylesterase from acerola (Malpighia glabra L.)
Authors: de Assis Sandra Aparecida , Martins Antônio Baldo Geraldo , de Faria Oliveira Olga Maria Mascarenhas
Published: May 2007

The enzyme pectinmethylesterase (PME) from acerola was extracted and purified by gel anion‐exchange chromatography (Q Sepharose) and filtration on Sephadex G‐100. The results showed two different PME isoforms (PME1 and PME2), with molecular masses of 25.10 and 5.20 kDa, respectively. PME1 specific activity increased by 9.63% after 60 min incubation at 98 °C, while PME2 retained 66% of its specific activity under the same conditions. The Km values of PME1, PME2 and concentrated PME were 0.94, 0.08 and 0.08 mg mL−1, respectively. The Vmax value of PME1, PME2 and concentrated were 204.08, 2, 158.73 and 2.92 µmol min−1 mg−1 protein, respectively. Copyright © 2007 Society of Chemical Industry
Capillary electrochromatography of proteins and peptides
Authors: Mikšík Ivan , Sedláková Pavla
Published: May 2007

This review summarizes applications of CEC for the analysis of proteins and peptides. This “hybrid” technique is useful for the analysis of a broad spectrum of proteins and peptides and is a complementary approach to liquid chromatographic and capillary electrophoretic analysis. All modes of CEC are described – granular packed columns, monolithic stationary phases as well as open‐tubular CEC. Attention is also paid to pressurized CEC and the chip‐based platform.
Applications of S‐theory in the study of soil physical degradation and its consequences
Authors: Dexter A. R. , Czyż E. A.
Published: May 2007

The S‐theory for soil physical quality is introduced. It is shown how values of S can be determined from the water retention characteristic curve. It is also explained how, when experimental data are not available, pedotransfer functions can be used to obtain estimates of S. Although S was first introduced as an index of soil physical quality, it is being increasingly found that it is a useful numerical quantity that can be used in equations for prediction of a range of soil physical properties. Its use is illustrated with examples for hydraulic conductivity, friability, tillage, compaction, penetrometer resistance, plant‐available water, root growth and readily dispersible clay. The main merit of S derives from the fact that given values of S have the same meaning and consequences in different soils. It is described how S can be used to identify areas of land where physical degradation or amelioration are taking place, and to evaluate management practices that will give sustainable land use. Copyright © 2007 John Wiley & Sons, Ltd.
UV‐Assisted Surface Modification of Polybutadiene with Phosphorus‐Containing Groups
Authors: Buchgraber Christian , Svagera Robert , Ebel Maria F. , Schröttner Hartmuth , Kern Wolfgang
Published: May 2007

A new method for the modification of polymer surfaces with phosphorus‐containing groups is described. Films of polybutadiene were UV‐irradiated in the presence of PBr3 vapor as a photoreactive agent. After subsequent reaction with water under aerobic conditions, phosphonic acid groups were present at the surface. Similarly, methanolysis yielded phosphonic acid esters at the polymer surface. These conversions have been evidenced by IR and XPS. Using contact masks, a patterned modification with phosphorus‐containing groups was achieved. The UV‐induced attachment of phosphonic acid groups onto polymer surfaces is a way towards biocompatible surfaces, e.g. for prosthetic materials.

magnified image
Synthesis of Poly(lauryl acrylate) by Single‐Electron Transfer/Degenerative Chain Transfer Living Radical Polymerization Catalyzed by Na2S2O4 in Water
Authors: Coelho Jorge F. J. , Carvalho Erica Y. , Marques Dina S. , Popov Anatoliy V. , Goncalves Pedro M. , Gil Maria H.
Published: May 2007

Living radical polymerization of lauryl acrylate was achieved by SET/DTLRP in water catalyzed by sodium dithionite. The work describes the synthesis of a highly hydrophobic and polar monomer in aqueous medium. The plots of $\overline M _{\rm n}$ versus conversion and ln[M]0/[M] versus time are linear, indicating a controlled polymerization. This method leads to α,ω‐diiodopoly(lauryl acrylate)s that can be further functionalized. The MWDs were determined using a combination of three detectors: RALLS, DV, and RI. The method studied in this work represents a possible route to prepare well‐tailored macromolecules made of LA in environment friendly reaction medium. The syndiotactic content is 75%.

magnified image
Macromol. Chem. Phys. 11/2007
Authors: Oishi Motoi , Hayashi Hisato , Uno Teppei , Ishii Takehiko , Iijima Michihiro , Nagasaki Yukio
Published: May 2007

Cover: One‐pot synthesis of pH‐responsive PEGylated nanogels containing gold nanoparticles was successfully carried out through the autoreduction of HAuCl4 with EGylated nanogels as the “nanoreactor”. The surface plasmon band of the PEGylated nanogel containing gold nanoparticles was shifted in response to pH. Further details can be found in the Full Paper by M. Oishi, H. Hayashi, T. Uno, T. Ishii, M. Iijima, and Y. Nagasaki* on page 1176.