bluuebunny/crossref_metadata_2025 huggingface dataset:
Hexagon‐free subgraphs of hypercubes
Authors: Conder Marston
Published: May 2007

It is shown (for all n ≥ 3) that the edges of the n‐cube can be 3‐colored in such a way that there is no monochromatic 4‐cycle or 6‐cycle. © 1993 John Wiley & Sons, Inc.
Collapsible graphs and matchings
Authors: Chen Zhi‐Hong , Lai Hong‐Jian
Published: May 2007

A graph G is collapsible if for every even subset R ⊆ V(G), there is a spanning connected subgraph of G whose set of odd degree vertices is R. A graph is reduced if it does not have nontrivial collapsible subgraphs. Collapsible and reduced graphs are defined and studied in [4]. In this article, we obtain a lower bound on the size of a maximum matching in a reduced graph. As an application, we verify and strengthen the Benhocine, Clark, Köhler, and Veldman conjecture [1], when restricted to 3‐edge‐connected graphs, by showing that for n large, a simple graph G with order n and with k′(G) ≥ 3 is collapsible or is contractible to the Petersen graph if for each edge uv ∈ E(G), d(u) + d(v) ≥ (n/5) − 2. We also characterize the extremal graphs. © 1993 John Wiley & Sons, Inc.
Generating all 3‐connected 4‐regular planar graphs from the octahedron graph
Authors: Broersma H. J. , Duijvestijn A. J. W. , Göbel F.
Published: May 2007

We prove that all 3‐connected 4‐regular planar graphs can be generated from the Octahedron Graph, using three operations. We generated these graphs up to 15 vertices inclusive. Moreover, by including a fourth operation we obtain an alternative to a procedure by Lehel to generate all connected 4‐regular planar graphs from the Octahedron Graph. © 1993 John Wiley & Sons, Inc.
A note on maximal triangle‐free graphs
Authors: Goddard Wayne , Kleitman Daniel J.
Published: May 2007

We show that a maximal triangle‐free graph on n vertices with minimum degree δ contains an independent set of 3δ − n vertices which have identical neighborhoods. This yields a simple proof that if the binding number of a graph is at least 3/2 then it has a triangle. This was conjectured originally by Woodall. © 1993 John Wiley & Sons, Inc.
On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs
Authors: Cnrs Jean‐Claude Bermond , Hell Pavol
Published: May 2007

Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in‐ and outdegree d have arc‐chromatic index 2d. In order to do this, we introduce the concept of even 1‐factorizations. An even 1‐factor of a digraph is a spanning subgraph consisting of vertex disjoint loops and even cycles; an even 1‐factorization is a partition of the arcs into even 1‐factors. We prove that if a digraph admits an even 1‐factorization, then so does its line digraph. (In fact, we show that the line digraph admits an even 1‐factorization even under a weaker assumption discussed below.) As a consequence, we derive the above property of the Kautz and de Bruijn digraphs relevant to packet radio networks. © 1993 John Wiley & Sons, Inc.
Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
Authors: Woodall D. R.
Published: May 2007

Zarankiewicz's conjecture, that the crossing number of the complete‐bipartite graph Km, n is [1/2 m] [1/2 (m] −1) [1/2 n] [1/2 (n −1)], was proved by Kleitman when min(m, n) ≤ 6, but was unsettled in all other cases. The cyclic‐order graph COn arises naturally in the study of this conjecture; it is a vertex‐transitive harmonic diametrical (even) graph. In this paper the properties of cyclic‐order graphs are investigated and used as the basis for computer programs that have verified Zarankiewicz's conjecture for K7,7 and K7,9; thus the smallest unsettled cases are now K7,11 and K9,9. © 1993 John Wiley & Sons, Inc.
Disjoint Hamiltonian cycles in fan 2k‐type graphs
Authors: Sanming Zhou
Published: May 2007

It is conjectured that a 2(k + 1)‐connected graph of order p contains k + 1 pairwise disjoint Hamiltonian cycles if no two of its vertices that have degree less than 1/2 + 2k are distance two apart. This is proved in detail for k = 1. Similar arguments establish the conjecture for k = 2. © 1993 John Wiley & Sons, Inc.
An upper bound for the Folkman number F(3, 3; 5)
Authors: Erickson Martin
Published: May 2007

Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green‐red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.
The projective plane crossing number of C3 × Cn
Authors: Riskin Adrian
Published: May 2007

In this paper, we show that the projective plane crossing number of the graphs C3 × Cn is n ‐ 1 for n ≤ 5 and 2 for n = 4. As far as we can tell from the literature, this is the first infinite family of graphs whose crossing number is known on a single surface other than the plane. © 1993 John Wiley & Sons, Inc.
Sufficient conditions for equality of connectivity and minimum degree of a graph
Authors: Topp Jerzy , Volkmann Lutz
Published: May 2007

For a graph G, let n(G), κ(G) and δ(G) denote the order, the connectivity, and the minimum degree of G, respectively. The paper contains some conditions on G implying κ(G) = δ(G). One of the conditions is that n(G) ≤ δ(G)(2p −1)/(2p −3) if G is a p‐partite graph. © 1993 John Wiley & Sons, Inc.
A sufficient condition for a regular graph to be class 1
Authors: Hilton A. J. W. , Zhao Cheng
Published: May 2007

The core GΔ of a simple graph G is the subgraph induced by the vertices of maximum degree. It is well known that the Petersen graph is not 1‐factorizable and has property that the core of the graph obtained from it by removing one vertex has maximum degree 2. In this paper, we prove the following result. Let G be a regular graph of even order with d(G) ≥ 3. Suppose that G contains a vertex ν such that the core of G\ν has maximum degree 2. If G is not the Petersen graph, then G is 1‐factorizable. © 1993 John Wiley & Sons, Inc.
On tree factorizations of Kn
Authors: Yu Min‐Li
Published: May 2007

In this paper we exhibit a class of trees with the property that if Tk is a tree on k vertices that belongs to this class, then necessary and sufficient conditions for Kn to have a Tk‐factorization are simply n = 0 (mod k) and n = 1 (mod 2(k ‐ 1)). (This class is large and in particular contains all caterpillars with an odd number of vertices.) As a corollary we obtain necessary and sufficient conditions for the existence of a K1,k‐1‐factorization of Kn, which previously had only been known to be asymptotically sufficient. © 1993 John Wiley & Sons, Inc.
On the minimum number of edge‐disjoint complete m‐partite subgraphs into which Kn can be decomposed
Authors: Huang Qing‐Xue
Published: May 2007

Let αm(n) denote the minimum number of edge‐disjoint complete m‐partite subgraphs into which Kn can be decomposed. In [2] the author proved that when m ≥ 3, if (i) n ≡ m and n ≡ m (mod m −1), or (ii) b ∈ [2, m −1], n ≥ b(m −1) + m − (b −1), and n ≡ b(m −1) + m − (b −1) (mod m− 1), then αm(n) = ⌊(n + m −3)/(m −1)⌋ (= ⌊(n −1)/(m −1)⌋), and that for every integer n, if Kn has an edge‐disjoint complete m‐partite subgraph decomposition, then αm(n) ≥ ⌊(n− 1)/(m− 1)⌋.

In this paper we generally discuss the question as to which integers n's satisfy (or do not) αm(n) = ⌊(n −1)/(m −1)⌋. Here we also study the methods to find these integers; the methods are themselves interesting. Our main results are Theorem 2.11, 2.12, and 2.16. Besides, Theorem 2.4 and 2.6 are interesting results too. © 1993 John Wiley & Sons, Inc.
Two trees in maximal planar bipartite graphs
Authors: Ringel Gerhard
Published: May 2007

It is proven that each maximal planar bipartite graph is decomposable into two trees. © 1993 John Wiley & Sons, Inc.
Reconstructing the number of copies of a valency‐labeled finite graph in an infinite graph
Authors: King A. J. H. , Nash‐Williams C. St. J. A.
Published: May 2007

Suppose that G, H are infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such that G ‐ ξ ≅ H ‐ Ψ(ξ) for every ξ ∼ V(G). Let J be a finite graph and /(π) be a cardinal number for each π ≅ V(J). Suppose also that either /(π) is infinite for every π ≅ V(J) or J has a connected subgraph C such that /(π) is finite for every π ≅ V(C) and every vertex in V(J)/V(C) is adjacent to a vertex of C. Let (J, I, G) be the set of those subgraphs of G that are isomorphic to J under isomorphisms that map each vertex π of J to a vertex whose valency in G is /(π). We prove that the sets (J, I, G), m(J, I, H) have the same cardinality and include equal numbers of induced subgraphs of G, H respectively.
Radius two trees specify χ‐bounded classes
Authors: Kierstead H. A. , Penrice S. G.
Published: May 2007

A class of graphs χ is said to be χ‐bounded, with χ‐binding function f, if for all G ϵ Γ, χ (G) ≦ f (ω(G)), where χ(G) is the chromatic number of G and ω(G) is the clique number of G. It has been conjectured that for every tree T, the class of graphs that do not induce T is χ‐bounded. We show that this is true in the case where T is a tree of radius two.
Short cycle covers of cubic graphs
Authors: Fan Genghua
Published: May 2007

Let G be a bridgeless cubic graph. We prove that the edges of G can be covered by circuits whose total length is at most (44/27) |E(G)|, and if Tutte's 3‐flow Conjecture is true, at most (92/57) |E(G)|.
On zero sum Ramsey numbers: Multiple copies of a graph
Authors: Bialostocki A. , Dierker P.
Published: May 2007

As a consequence of our main result, a theorem of Schrijver and Seymour that determines the zero sum Ramsey numbers for the family of all r‐hypertrees on m edges and a theorem of Bialostocki and Dierker that determines the zero sum Ramsey numbers for r‐hypermatchings are combined into a single theorem. Another consequence is the determination of zero sum Ramsey numbers of multiple copies of some small graphs.
Smallest (1, 2)‐eulerian weight and shortest cycle covering
Authors: Zhao Cheng
Published: May 2007

The concept of a (1, 2)‐eulerian weight was introduced and studied in several papers recently by Seymour, Alspach, Goddyn, and Zhang. In this paper, we proved that if G is a 2‐connected simple graph of order n (n ≧ 7) and w is a smallest (1, 2)‐eulerian weight of graph G, then |Ew=even | n ‐ 4, except for a family of graphs. Consequently, if G admits a nowhere‐zero 4‐flow and is of order at least 7, except for a family of graphs, the total length of a shortest cycle covering is at most | V(G) | + |E(G) |‐ 4. This result generalizes some previous results due to Bermond, Jackson, Jaeger, and Zhang.
Path factors of bipartite graphs
Authors: Wang Hong
Published: May 2007

A path on n vertices is denoted by Pn. For any graph H, the number of isolated vertices of H is denoted by i(H). Let G be a graph. A spanning subgraph F of G is called a {P3, P4, P5}‐factor of G if every component of F is one of P3, P4, and P5. In this paper, we prove that a bipartite graph G has a {P3, P4, P5}‐factor if and only if i(G − S − M) ≦ 2|S| + |M| for all S ⊆ V(G) and independent M ⊆ E(G).
On greene's theorem for digraphs
Authors: Hartman Irith Ben‐Arroyo , Saleh Fathi , Hershkowitz Daniel
Published: May 2007

Greene's Theorem states that the maximum cardinality of an optimal k‐path in a poset is equal to the minimum k‐norm of a k‐optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general digraphs in which an optimal k‐path contains a path of cardinality one. This implies the validity of the conjecture for all bipartite digraphs. We also extend Greene's Theorem to all split graphs.
On a conjecture about the generalized exponent of primitive matrices
Authors: Liu Bolian , Li Qiaoliang
Published: May 2007

In this paper the conjecture on the kth upper multiexponent of primitive matrices proposed by R.A. Brualdi and Liu are completely proved.
On 3‐regular graphs having crossing number at least 2
Authors: McQuillan Dan , Richter R. Bruce
Published: May 2007

We give a planar proof of the fact that if G is a 3‐regular graph minimal with respect to having crossing number at least 2, then the crossing number of G is 2.
On hamiltonian‐connected graphs
Authors: Gould Ronald J. , Yu Xingxing
Published: May 2007

One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ≅ V(G), then G is hamiltonian‐connected. We generalize this result using set degrees. That is, for S ⊂ V(G), let deg S = |x≅S N(x)|, where N(x) = {v|xv ≅ E(G)} is the neighborhood of x. In particular we show: In a 3‐connected graph G, if deg S1 + deg S2 ≧ |V(G)| + 1 for each pair of distinct 2‐sets of vertices S1, S2 ⊂ V(G), then G is hamiltonian‐connected.

Several corollaries and related results are also discussed.
Sequences realizable by maximal k‐degenerate graphs
Authors: Borowiecki M. , Ivančo J. , Mihók P. , Semanišin G.
Published: May 2007

A graph G is called k‐degenerate if every subgraph of G has a vertex of degree at most k. A k‐degenerate graph G is maximal k‐degenerate if for every edge e ϵ E(G), G + e is not k‐degenerate. Necessary and sufficient conditions for the sequence II = (d1, d2, ⃛, dp) to be a degree sequence of a maximal k‐degenerate graph G are presented. © 1995 John Wiley & Sons, Inc.
The crossing number of c4 × c4
Authors: Dean Alice M. , Bruce Richter R.
Published: May 2007

We prove that the crossing number of C4 × C4 is 8. © 1995 John Wiley & Sons, Inc.
Path covers of weighted graphs
Authors: Fan Genghua
Published: May 2007

Let (G, w) denote a simple graph G with a weight function w : E(G) ← {0, 1, 2}. A path cover of (G, w) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex v, w(v) is the sum of the weights of the edges incident with v; v is called an odd (even) vertex if w(v) is odd (even). We prove that if every vertex of (G, w) is incident with at most one edge of weight 2, then (G, w) has a path cover P such that each odd vertex occurs exactly once, and each even vertex exactly twice, as an end of a path of P. We also prove that if every vertex of (G, w) is even, then (G, w) has a path cover P such that each vertex occurs exactly twice as an end of a path of P. © 1995 John Wiley & Sons, Inc.
An eulerian trail traversing specified edges in given order
Authors: Mao‐cheng Cai , Fleischner Herbert
Published: May 2007

The following results are proved in this paper. Let G be a 2k‐edge‐connected eulerian graph. (i) For every set {e1, e2, ⃛, e2k+1} ⊆ E(G) there is an eulerian trail T of the form e1, e2, ⃛, e2k+1, ⃛. (ii) For every set E* = {e1, e2, ⃛, ek} ⊆ E(G) there is an eulerian trail T = e1, ⃛, e2, ⃛, ek, ⃛ in which the elements of E* are traversed in accordance with a prescribed orientation. © 1995 John Wiley & Sons, Inc.
Coloring graph bundles
Authors: Klavžar Sandi , Mohar Bojan
Published: May 2007

Graph bundles generalize the notion of covering graphs and products of graphs. Several results about the chromatic numbers of graph bundles based on the Cartesian product, the strong product and the tensor product are presented. © 1995 John Wiley & Sons, Inc.
Cycles through vertices of large maximum degree
Authors: Jackson Bill
Published: May 2007

Let G be a 2‐connected graph on n vertices with maximum degree k where n ≤ 3k ‐ 2. We show that there is a cycle in G that contains all vertices of degree k. © 1995 John Wiley & Sons, Inc.
Embedding edge‐colorings into 2‐edge‐connected k‐factorizations of kkn+1
Authors: Rodger C. A. , Wantland E. B.
Published: May 2007

In this paper we use the Hilton method of amalgamations to give a different proof of a theorem of Nash‐Williams that finds necessary and sufficient conditions for the embedding of an edge‐colored Kv into an edge‐colored Kv in which the edges of each color induce a 2‐edge‐connected k‐factor. © 1995 John Wiley & Sons, Inc.
Isomorphic factorizations of trees
Authors: Heinrich Katherine , Horak Peter
Published: May 2007

A tree is even if its edges can be colored in two colors so that the monochromatic subgraphs are isomorphic. All even trees of maximum degree 3 in which no two vertices of degrees 1 or 3 are adjacent are determined. It is also shown that, for every n, there are only finitely many trees of maximum degree 3 and with n vertices of degree 3 that are not even. © 1995 John Wiley & Sons, Inc.
Bipartite labelings of trees and the gracesize
Authors: Rosa Alexander , Širáň Jozef
Published: May 2007

Let T = (V, E) be a tree whose vertices are properly 2‐colored. A bipartite labeling of T is a bijection f: V ← {0, 1, ⃛, | E |} for which there is a k such that whenever f(u) ≤ k < f(v), then u and v have different colors. The α‐size of the tree T is the maximum number of distinct values of the induced edge labels |f(u) ‐ f(v)|, uv ϵ E, taken over all bipartite labelings f of T.

We investigate the asymptotic behavior of the α‐size of trees. Let α(n) be the smallest α‐size among all the trees with n edges. As our main result we prove that 5(n + 1)/7 ≤ α(n) ≤ (5n + 9)/6. A connection with the graceful tree conjecture is established, in that every tree with n edges is shown to have “gracesize” at least 5n/7. © 1995 John Wiley & Sons, Inc.
Tournament games and positive tournaments
Authors: Fisher David C. , Ryan Jennifer
Published: May 2007

Given a tournament T, the tournament game on T is as follows: Two players independently pick a node of T. If both pick the same node, the game is tied. Otherwise, the player whose node is at the tail of the arc connecting the two nodes wins. We show that the optimal mixed strategy for this game is unique and uses an odd number of nodes.

A tournament is positive if the optimal strategy for its tournament game uses all of its nodes. The uniqueness of the optimal strategy then gives a new tournament decomposition: any tournament can be uniquely partitioned into positive subtournaments P1, P2, ⃛,Pk, so Pi “beats” Pj for all 1 ≤ i > j ≤ k. We count the number of n node positive tournaments and list them for n ≤ 7. © 1995 John Wiley & Sons, Inc.
An algebraic characterization of planar graphs
Authors: Archdeacon Dan , Paul Bonnington C. , Little Charles H. C.
Published: May 2007

A cycle in a graph is a set of edges that covers each vertex an even number of times. A cocycle is a collection of edges that intersects each cycle in an even number of edges. A bicycle is a collection of edges that is both a cycle and a cocycle. The cycles, cocycles, and bicycles each form a vector space over the integers modulo two when addition is defined as symmetric difference of sets. In this paper we examine the relationship between the left‐right paths in a planar graph and the cycle space, cocylce space, and bicycle space. We show that planar graphs are characterized by the existence of a diagonal—a double cover by tours that interacts with the cycle space, cocycle space, and bicycle space in a special manner. This generalizes a result of Rosenstiehl and Read that characterized those planar graphs with no nonempty bicycles. © 1995 John Wiley & Sons, Inc.
On the join of graphs and chromatic uniqueness
Authors: Chia G. L.
Published: May 2007

A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let G be a chromatically unique graph and let Km denote the complete graph on m vertices. This paper is mainly concerned with the chromaticity of Km + G where + denotes the join of graphs. Also, it is shown that a large family of connected vertextransitive graphs that are not chromatically unique can be obtained by taking the join of some vertex‐transitive graphs. © 1995 John Wiley & Sons, Inc.
On the two‐edge‐colorings of perfect graphs
Authors: Hoàng Chính T.
Published: May 2007

We investigate the conjecture that a graph is perfect if it admits a two‐edge‐coloring such that two edges receive different colors if they are the nonincident edges of a P4 (chordless path with four vertices). Partial results on this conjecture are given in this paper. © 1995 John Wiley & Sons, Inc.
Lower bounds for the average genus
Authors: Chen Jianer , Gross Jonathan L. , Rieper Robert G.
Published: May 2007

Two lower bounds are obtained for the average genus of graphs. The average genus for a graph of maximum valence at most 3 is at least half its maximum genus, and the average genus for a 2‐connected simplicial graph other than a cycle is at least 1/16 of its cycle rank. © 1995 John Wiley & Sons, Inc.
Path decompositions of multigraphs
Authors: Cai Leizhen
Published: May 2007

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and μ(x) respectively. Define

Ø(x) = the least even integer ≥ μ(x), if d(x) is even, the least odd integer ≥ μ(x), if d(x) is odd.

In this paper it is shown that every multigraph G admits a faithful path decomposition—a partition P of the edges of G into simple paths such that every vertex x of G is an end of exactly Ø(x) paths in P. This result generalizes Lovász's path decomposition theorem, Li's perfect path double cover theorem (conjectured by Bondy), and a result of Fan concerning path covers of weighted graphs. It also implies an upper bound on the number of paths in a minimum path decomposition of a multigraph, which motivates a generalization of Gallai's path decomposition conjecture. © 1995 John Wiley & Sons, Inc.
R(4, 5) = 25
Authors: McKay Brendan D. , Radziszowski Stanislaw P.
Published: May 2007

The Ramsey number R(4, 5) is defined to be the least positive integer n such that every n‐vertex graph contains either a clique of order 4 or an independent set of order 5. With the help of a long computation using novel techniques, we prove that R(4, 5) = 25. © 1995 John Wiley & Sons, Inc.
Cycles in bipartite graphs and an application in number theory
Authors: N. Sárközy Gábor
Published: May 2007

Let G = G(A, B) be a bipartite graph with |A| = u, |B| = v, and let / be a positive integer. In this paper we prove the following result: If v ≤ u, uv ≤ n, m = |E(G)|, and m ≥ max{180/u, 20/n1/2(1+(1/l))}, then G contains a C2/. © 1995 John Wiley & Sons, Inc.
Paths, cycles, and arc‐connectivity in digraphs
Authors: Su Xiang‐Ying
Published: May 2007

In this paper we prove the following theorem: Let D be a k‐arcconnected digraph (multiple arcs allowed). If x is a vertex of D and / is an integer with / ≤ k, then for any / disjoint arc pairs {f1, g1}, ⃛, {f1, g1}, where f1, ⃛, f1 are arcs with head at x and g1, ⃛, g1 are arcs with tail at x, there exist in D / arc‐disjoint cycles C1, ⃛, C1 such that {fi, gi} ⊆ E(Ci) for each i (E(Ci) denotes the arc set of Ci) and such that D ‐ ∪ E(Ci) is (k ‐ 1)‐arc‐connected. Several interesting results are deduced from this theorem. Our results generalize the early works of Mader (“On a Property of n‐Edge‐Connected Digraphs,” Combinatorica, vol. 1 [1981], pp. 385‐386) and Shiloach (“Edge‐Disjoint Branching in Directed Multigraphs,” Information Processing Letters, vol. 8 [1979], pp. 24‐27). An extension of Mader's theorem about admissible liftings of digraphs is also obtained in this paper. © 1995 John Wiley & Sons, Inc.
Competitive inheritance and limitedness of graphs
Authors: Wang Chi
Published: May 2007

The study of competition number of graphs has brought many interesting problems to graph theory and combinatorics. However, little is known about what makes the competition number of a graph small or large. In this paper, we introduce competitive inheritance and limitedness of graphs. We show that most graphs studied in the literature of competition graphs possess the inheritance property on their competition number. We characterize the limitedness of graphs on competition number by forbidden induced subgraphs. Our results also prove a conjecture of Opsut on competition number for a new class of graphs. © 1995 John Wiley & Sons, Inc.
Realization of digraphs by preferences based on distances in graphs
Authors: Gu Weizhen , Reid K. B. , Schnyder Walter
Published: May 2007

Consider a graph G with two distinguished sets of vertices: the voters and the candidates. A voter v prefers candidate x to candidate y if d(v, x) < d(v, y). This preference relation defines an asymmetric digraph whose vertices are the candidates, in which there is an arc from candidate x to candidate y if and only if more voters prefer x to y than prefer y to x. T. W. Johnson and P. J. Slater (“Realization of Majority Preference Digraphs by Graphically Determined Voting Patterns,” Congressus Numerantium, vol. 67 [1988] 175‐186) have shown that each asymmetric digraph of order n can be realized in this way using a graph of order O(n2). We present a new construction reducing the quadratic upper bound to a linear bound. © 1995 John Wiley & Sons, Inc.
The size of graphs without nowhere‐zero 4‐flows
Authors: Lai Hong‐Jian
Published: May 2007

Let G be a 2‐edge‐connected simple graph with order n. We show that if | V(G)| ≤ 17, then either G has a nowhere‐zero 4‐flow, or G is contractible to the Petersen graph. We also show that for n large, if | V(G)| n − 17/2 + 34, then either G has a nonwhere‐zero 4‐flow, or G can be contracted to the Petersen graph. © 1995 John Wiley & Sons, Inc.
Generalized degree conditions for graphs with bounded independence number
Authors: Faudree Ralph , Gould Ronald J. , Lesniak Linda , Lindquester Terri
Published: May 2007

We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac‐type bound on this degree in conjunction with a bound on the independence number of a graph is sufficient to imply certain hamiltonian properties in graphs. For K1,m‐free grphs we obtain generalizations of known results. In particular we show:

Theorem. Let r ≥ 1 and m ≥ 3 be integers. Then for each nonnegative function f(r, m) there exists a constant C = C(r, m, f(r, m)) such that if G is a graph of order n (n ≥ r, n > m) with δr(G) ≥ (n/3) + C and β (G) ≥ f(r, m), then (a) G is traceable if δ(G) ≥ r and G is connected; (b) G is hamiltonian if δ(G) ≥ r + 1 and G is 2‐connected; (c) G is hamiltonian‐connected if δ(G) ≥ r + 2 and G is 3‐connected. © 1995 John Wiley & Sons, Inc.
The fractional chromatic number of mycielski's graphs
Authors: Larsen Michael , Propp James , Ullman Daniel
Published: May 2007

James Propp

The most familiar construction of graphs whose clique number is much smaller than their chromatic number is due to Mycielski, who constructed a sequence Gn of triangle‐free graphs with X(Gn) = n. In this article, we calculate the fractional chromatic number of Gn and show that this sequence of numbers satisfies the unexpected recurrence an+1 = an + (1/an). © 1995 John Wiley & Sons, Inc.
A polynomial time algorithm recognizing link trees
Authors: Bugata Peter , Nagy Attila , Vávra Roman
Published: May 2007

The link of a vertex v of a graph G is the subgraph induced by all vertices adjacent to v. If all the links of G are isomorphic to a finite graph L, then G is called a realization of L, and L is called a link graph.

At the Smolenice symposium of 1963, Zykov posed the problem of recognizing link graphs. There are two versions of that problem, namely the finite (the existence of a finite realization is required) and the infinite one.

Bulitko (see “On Graphs with Prescribed Links of Vertices” [in Russian], Trudy mat. inst. im. Steklova, Vol. 133, 1973, pp. 78‐94) proved that the infinite version is algorithmically unsolvable. The solution of both versions is known only for special classes of graphs as paths, cycles, and graphs homeomorphic to a star (see M. Brown and R. Connelly, “On Graphs with a Constant Link I,” New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 19‐51; On Graphs with a Constant Link II, Discrete Mathematics, Vol. 11, 1975, pp. 199‐232). The finite version for trees with less than 10 vertices has been solved by Blass, Harary, and Miller (see “Which Trees Are Link Graphs?” Journal of Combinatorics Theory Series B, Vol. 29, 1980, pp. 277‐292).

Trees that are link graphs are called link trees. Using some previous results of Bulitko (see “On a Recursive Property of Block‐Complete Graphs” [in Russian], Proceedings of Czechoslovak Conference on Graphs, Zemplínska Širava, 1978, p. 20‐30), we present a polynomial time algorithm recognizing link trees. The applied methods have some remarkable consequences concerning the study of link graphs. © 1995 John Wiley & Sons, Inc.
Enumeration of trees by inversions
Authors: Gessel Ira M. , Sagan Bruce E. , Yeh Yeong‐Nan
Published: May 2007

Mallows and Riordan “The Inversion Enumerator for Labeled Trees,” Bulletin of the American Mathematics Society, vol. 74 [1968] pp. 92‐94) first defined the inversion polynomial, Jn(q) for trees with n vertices and found its generating function. In the present work, we define inversion polynomials for ordered, plane, and cyclic trees, and find their values at q = 0, ± 1. Our techniques involve the use of generating functions (including Lagrange inversion), hypergeometric series, and binomial coefficient identities, induction, and bijections. We also derive asymptotic formulae for those results for which we do not have a closed form. © 1995 John Wiley & Sons, Inc.
The 2‐intersection number of paths and bounded‐degree trees
Authors: Jacobson Michael S. , Kézdy André E. , West Douglas B.
Published: May 2007

We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The 2‐intersection number θ2(G) of a graph G is the minimum size of the union of sets in such a representation. We prove that the maximum order of a path that can be represented in this way using t elements is between (t2 ‐ 19t + 4)/4 and (t2 ‐ t + 6)/4, making θ2(Pn) asymptotic to 2√n. We also show the existence of a constant c depending on ϵ such that, for any tree T with maximum degree at most d, θ2(T) ≤ c(√n)1+ϵ. When the maximum degree is not bounded, there is an n‐vertex tree T with θ2(T) > .945n2/3. © 1995 John Wiley & Sons, Inc.
Oriented hamilton cycles in digraphs
Authors: Häggkvist Roland , Thomason Andrew
Published: May 2007

We show that a directed graph of order n will contain n‐cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 + n‐1/6)n and n is sufficiently large. © 1995 John Wiley & Sons, Inc.
Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
Authors: Gutin G.
Published: May 2007

A digraph obtained by replacing each edge of a complete m‐partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is calied a semicomplete m‐partite digraph. We describe results (theorems and algorithms) on directed walks in semicomplete m‐partite digraphs, including some recent results concerning tournaments. © 1995 John Wiley & Sons, Inc.
Graphs with least number of colorings
Authors: Sakaloglu A. , Satyanarayana A.
Published: May 2007

A λ‐coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. Let Ω (n,e) be the collection of all connected n‐point and e‐edge graphs and let Ωp(n,e) be the planar graphs of Ω(n, e). This paper characterizes the graphs that minimize the number of λ‐colorings in Ω(n, e) for all λ > 1 and Ωp(n,e) for all λ.4. © 1995 John Wiley & Sons, Inc.
Three‐dimensional fine structural reconstruction of the nose sensory structures of Acrobeles complexus compared to Caenorhabditis elegans (Nematoda: Rhabditida)
Authors: Bumbarger Daniel J. , Crum John , Ellisman Mark H. , Baldwin James G.
Published: May 2007

Nematode sensory structures can be divided into two classes; cuticular sensillae, with dendrites ending outside the epidermis, and internal receptors, that typically are single dendrites terminating within the body cavity. Fine structure of the former has been described completely in more than a dozen nematode taxa, while the latter were previously only well understood in the microbial feeder Caenorhabditis elegans. The distantly related nematode Acrobeles complexus has a similar ecology and together the two span a clade representing a large proportion of nematode biodiversity. The cuticular sensillae and internal receptors of A. complexus are here shown to be remarkably similar in number, arrangement, and morphology to those of C. elegans. Several key differences are reported that likely relate to function, and suggest that this nematode has a cuticular sensillum morphology that is closer to that of the common ancestor of the two taxa. Internal sensory receptors have more elaborate termini than those of C. elegans. The existence of a novel form of mechanoreceptor in A. complexus and spatial relationships between sensillum dendrites suggest differences between two classes of sensillae in how a touch‐response behavior may be mediated. J. Morphol., 2007. © 2007 Wiley‐Liss, Inc.
Quantitative evaluation of the binding of phenylarsenic species to glutathione, isotocin, and thioredoxin by means of electrospray ionization time‐of‐flight mass spectrometry
Authors: Schmidt Anne‐Christine , Neustadt Madlen , Otto Matthias
Published: May 2007

An attempt was made to quantitatively describe the binding of phenylarsenic species to thiol‐containing biomolecules using electrospray ionization mass spectrometry (ESI‐MS). The extent of the reactions of phenylarsine oxide (PAO) with the peptides glutathione and isotocin (ITC) and with the protein thioredoxin resulting in covalent AsS bonds were quantified by deriving the dependence of the corresponding ion signal intensities on the concentration of the reaction products. Problems complicating a quantitative evaluation of the mass spectra, such as signal suppression effects, were critically evaluated. Equilibrium constants for condensation reactions as well as formation constants for noncovalent associations were calculated by means of ESI‐MS signal intensities. The comparison of the reaction of PAO with different thiol reactants revealed the highest binding affinity for ITC followed by thioredoxin and a lower affinity to glutathione. Possibly, the intramolecular formation of RS‐As(C6H5)‐SR occurring in case of ITC and thioredoxin is favored over the intermolecular product involving two molecules glutathione even though the molecular mass of glutathione (307 g mol−1) is much smaller than that of ITC (966 g mol−1) and thioredoxin (11 688 g mol−1). A similar binding affinity for trivalent (K ≈ 1.6 × 10−3 l µmol−1) and pentavalent (K ≈ 1.6 × 10−3 and 1.0 × 10−3 l µmol−1) arsenic species was found for the formation of a noncovalent complex of glutathione with different phenylarsenic compounds. Copyright © 2007 John Wiley & Sons, Ltd.
Differential inductions of small heat shock protein 27 and 1‐Cys peroxiredoxin in reactive astrocytes in sulfatide‐deficient mouse spinal cord
Authors: Suzuki Ayaka , Yamaguchi Yoshihide , Hoshi Tomiko , Hayashi Akiko , Baba Hiroko
Published: May 2007

In myelinated fibers, various interactions among axons, oligodendrocytes, and astrocytes are present, particularly around the node of Ranvier. In the present study, we examined the protein composition of cerebroside sulfotransferase knockout (CST KO) mouse spinal cord by two‐dimensional gel electrophoresis to examine the molecular changes resulting from the disruption of paranodal junctions in addition to the sulfatide‐deficient condition. Interestingly, heat shock protein 27 (Hsp27) and 1‐cys peroxiredoxin (1‐Cys Prx) were both elevated in CST KO mice. Hsp27 was increased specifically in reactive astrocytes in the white matter, and the elevation was well correlated to the progression of neurologic symptoms. In contrast, 1‐Cys Prx was elevated both in white and gray matter astrocytes in CST KO mice. These results suggest that astrocytes do not always respond stereotypically, as they display differences in their activation in these two regions. To determine whether these changes are specific to the sulfatide‐deficient condition, spinal cords from CST KO mice and the hypomyelinating mutant shiverer mice were compared. The same distribution patterns of Hsp27 and 1‐Cys Prx were found in reactive astrocytes in both CST KO and shiverer mice, suggesting that paranodal disruption with progressive nodal changes may underlie the similar reaction of white matter astrocytes. In contrast, CST KO and shiverer mice showed distinctly different localization patterns of connexin 43 and connexin 47, suggesting that intercellular communication between astrocytes and oligodendrocytes was different in these mutants. These results suggest that astrocytes may respond differentially to individual white matter abnormalities and may modulate specific axonal functions. © 2007 Wiley‐Liss, Inc.
Micro‐Raman study of PET single fibres under high hydrostatic pressure: phase/conformation transition and amorphization
Authors: Paquin Raphaël , Limage Marie‐Hélène , Colomban Philippe
Published: May 2007

The micro/nano structural evolution of a PET single fibre under hydrostatic pressure has been studied by Raman micro spectroscopy in a diamond anvil cell (DAC). Different bands in the Raman spectra were used as probes: the low wavenumber collective modes (<250 cm−1) representative of the long‐range chain organization, as well as the stretching and bending amide and aromatic ring modes representative of the local chain behaviour. The in situ analysis at different pressures shows an evolution from an axial oriented trans‐conformation to an amorphous, isotropic material, i.e. the reverse transformation observed during the process of drawing the fibre from an isotropic amorphous precursor. Copyright © 2007 John Wiley & Sons, Ltd.
Raman spectroscopy as a tool for long‐term energetic material stability studies
Authors: Moore David S. , Lee Kien‐Yin
Published: May 2007

Raman spectroscopy is shown to be useful as a tool for long‐term stability studies. The stability of a novel submicron‐size γ‐polymorph form of the explosive HMX (octahydro‐1,3,5,7‐tetranitro‐1,3,5,7‐tetrazocine) was monitored up to 1 year using Raman spectroscopy. The preparation and characterization of this submicron HMX has been previously discussed. It is important to know the long‐term stability of this submicron γ‐polymorph material under ambient conditions for its eventual utilization. This submicron HMX material has been found to be stable both chemically and polymorphically (to the order of 1% impurity level), even though HMX normally converts to the β‐polymorph at ambient conditions. Copyright © 2007 John Wiley & Sons, Ltd.
Adjuvant radiation therapy is associated with improved survival for gallbladder carcinoma with regional metastatic disease
Authors: Mojica Pablo , Smith David , Ellenhorn Joshua
Published: May 2007

Background

Gallbladder carcinoma is a rare malignancy and is associated with dismal outcomes. The aim of this study was to better define the role of adjuvant radiation therapy in the management of gallbladder carcinoma.

Methods

The Surveillance, Epidemiological, and End Results (SEER) survey from the National Cancer Institute was queried from 1992 to 2002. Retrospective analysis was done. The end‐point of the study was overall survival.

Results

There were a total of 3,187 cases of gallbladder carcinoma in the registry from 1992 to 2002. Of the surgical group, 35% were stage I, 36% were stage II, 6% were stage III, and 21% were stage IV. Adjuvant radiation was used in 17% of the cases. The median survival for those patients receiving adjuvant radiation therapy was 14 months compared to an 8 months median survival for those treated without adjuvant radiation therapy (P ≤ 0.001). The survival benefit associated with radiation use was only presenting those patients with regional spread (P = 0.0001) and tumors infiltrating the liver (P = 0.011).

Conclusion

The use of adjuvant radiation therapy is associated with improved survival in patients with locally advanced gallbladder cancer or gallbladder cancer with regional disease. J. Surg. Oncol. 2007;96:8–13 © 2007 Wiley‐Liss, Inc.
Sur l'Existence de Fonctions Récurrentes
Authors: de Barros Constantino M.
Published: May 2007

Dans le présent travail, on introduit la notion de schéma de récurrence associé à un modèle et on démontre un résultat assez géneral (Théorème 1) assurant l'existence et l'unicité de fonctions récurrentes sous‐jacentes à des schémas de récurrence associés à des modèles naturels. L'application de ce résultat à des schémas de récurrence particuliers donne, comme une conséquence immédiate, parmi d'autres, le théorème de la definition par récurrence et le théorème de l'obtention de fonctions par récurrence primitive.
TERNARY OPERATIONS AS PRIMITIVE NOTIONS FOR PLANE GEOMETRY II
Authors: Pambuccian Victor
Published: May 2007

We proved in the first part [1] that plane geometry over Pythagorean fields is axiomatizable by quantifier‐free axioms in a language with three individual constants, one binary and three ternary operation symbols. In this paper we prove that two of these operation symbols are superfluous.
An order‐theoretic characterization of the Schütte‐Veblen‐Hierarchy
Authors: Weiermann Andreas
Published: May 2007

For f: On → On let supp(f): = ξ: 0, and let S := {f : On → On : supp(f) finite}. For f,g ϵ S define

f ≤ g : ↔ (∃h : On → On)[h one‐to‐one ⁁ (∀ξ)f(ξ) ≤ g(h(ξ))].

A function ψ : S → On is called monotonic increasing, if f(ξ)≤ψ(f) and if f ≤ g implies ψ (f) ≤ ψ(g). For a mapping ψ : S → On let Clψ(0) be the least set T of ordinals which contains 0 as an element and which is closed under the following rule: If f ϵ S, range(f) ⊆ T and supp(f) ⊆ T, then ψ(f) ϵ T. Let φ be the enumeration function of the class {ξ: (∃n)[ξ = ωn]}. Let φ be the induced Schütte‐Klammerterm‐function (see [11]) which generates the Schütte‐Veblen‐hierarchy of ordinals. Then φ is monotonic increasing. We show: If ψ: S → On is monotonic increasing, then otyp(Clφ(0)) ≤ min {ξ : ξ = Φ, where 1ξ(α) = 1 if α = ξ and 1ξ(α) = 0 if α ↔ = 0 if α ≠ ξ. For τ an ordinal let Sτ := {f ϵ S : supp(f) ⊆ τ}. A function ψ : Sτ → On is called τ‐monotonic increasing if fξ (f) and if f ≤ g implies ψ (f) ≤ (g). For a function ψ Sτ → On let Clψ(0) ↔ τ be the least set T of ordinals, which contains 0 as an element, such that if f ϵ Sτ and range (f) ϵ T, then ψ (f) ϵ T. We show: if ≥2 and if ψ Sτ → On is τ‐monotonic increasing, then otyp(Clψ(0) ↔ τ) ≤(1ψ). We also prove a generalization of this theorem in terms of well‐partial orderings. MSC: 03F15, 03E10, 06A06.
Measure independent Gödel speed‐ups and the relative difficulty of recognizing sets
Authors: Solomon Martin K.
Published: May 2007

We provide and interpret a new measure independent characterization of the Gödel speed‐up phenomenon. In particular, we prove a theorem that demonstrates the indifference of the concept of a measure independent Gödel speed‐up to an apparent weakening of its definition that is obtained by requiring only those measures appearing in some fixed Blum complexity measure to participate in the speed‐up, and by deleting the “for all r” condition from the definition so as to relax the required amount of speed‐up. We interpret our results as correlating the relative difficulty of mechanically recognizing theories with the relative power and the relative abstractness of the theories. We conclude by providing two open problems concerning possible similarities and relationships between the Blum speedability and Gödel speed‐up phenomena. MSC: 03D15, 03F20.
Ternary operations as primitive notions for constructive plane geometry III
Authors: Pambuccian Victor
Published: May 2007

This paper continues the investigations begun in [6] and continued in [7] about quantifier‐free axiomatizations of plane Euclidean geometry using ternary operations. We show that plane Euclidean geometry over Archimedean ordered Euclidean fields can be axiomatized using only two ternary operations if one allows axioms that are not first‐order but universal Lw1,w sentences. The operations are: the transport of a segment on a halfline that starts at one of the endpoints of the given segment, and the operation which produces one of the intersection points of a perpendicular on a diameter of a circle (which intersects that diameter at a point inside the circle) with that circle. MSC: 03F65, 51M05, 51M15.
Intermediate logics preserving admissible inference rules of heyting calculus
Authors: Rybakov Vladimir V.
Published: May 2007

The aim of this paper is to look from the point of view of admissibility of inference rules at intermediate logics having the finite model property which extend Heyting's intuitionistic propositional logic H. A semantic description for logics with the finite model property preserving all admissible inference rules for H is given. It is shown that there are continuously many logics of this kind. Three special tabular intermediate logics λ, 1 ≥ i ≥ 3, are given which describe all tabular logics preserving admissibility: a tabular logic λ preserves all admissible rules for H iff 7λ has width not more than 2 and is not included in each λ. MSC: 03B55, 03B20.
Finitary sequence spaces
Authors: Mandelkern Mark
Published: May 2007

This paper studies the metric structure of the space Hr of absolutely summable sequences of real numbers with at most r nonzero terms. Hr is complete, and is located and nowhere dense in the space of all absolutely summable sequences. Totally bounded and compact subspaces of Hr are characterized, and large classes of located, totally bounded, compact, and locally compact subspaces are constructed. The methods used are constructive in the strict sense. MSC: 03F65, 54E50.
A note on effective ultrapowers: Uniform failure of bounded collection
Authors: McLaughlin Thomas
Published: May 2007

By suitably adapting an argument of Hirschfeld (see [2, Chapter 9]), we show that there is a single Δ1 formula that defeats “bounded collection” for any model of II2 Arithmetic that is either a recursive ultrapower or an existentially complete model. Some related facts are noted. MSC: 03F30, 03C62.
Typical ambiguity and elementary equivalence
Authors: Dzierzgowski Daniel
Published: May 2007

A sentence of the usual language of set theory is said to be stratified if it is obtained by “erasing” type indices in a sentence of the language of Russell's Simple Theory of Types. In this paper we give an alternative presentation of a proof the ambiguity theorem stating that any provable stratified sentence has a stratified proof. To this end, we introduce a new set of ambiguity axioms, inspired by Fraïssé's characterization of elementary equivalence; these axioms can be naturally used to give different proofs of the ambiguity theorem (semantic or syntactic, classical or intuitionistic). MSC: 03B15, 03F50, 03F55.
Derived sequences and reverse mathematics
Authors: Hirst Jeffry L.
Published: May 2007

One of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR0. This existence theorem is an intermediate step in a proof that a statement concerning topological comparability is equivalent to ATR0. In actuality, the full strength of ATR0 is used in proving the existence theorem. To show this, we will derive a statement known to be equivalent to ATR0, using only RCA0 and the assertion that every countable closed set has a derived sequence. We will use three of the subsystems of second order arithmetic defined by H. Friedman ([3], [4]), which can be roughly characterized by the strength of their set comprehension axioms. RCA0 includes comprehension for Δ definable sets, ACA0 includes comprehension for arithmetical sets, and ATR0 appends to ACA0 a comprehension scheme for sets defined by transfinite recursion on arithmetical formulas. MSC: 03F35, 54B99.
Non‐circular, non‐well‐founded set universes
Authors: Tzouvaras Athanassios
Published: May 2007

We show that there are universes of sets which contain descending ϵ‐sequences of length α for every ordinal α, though they do not contain any ϵ‐cycle. It is also shown that there is no set universe containing a descending ϵ‐sequence of length On. MSC: 03E30; 03E65.