bluuebunny/crossref_metadata_2025_split huggingface dataset:
Isomorphic factorizations of trees
Authors: Heinrich Katherine , Horak Peter 
Published: May 2007

AbstractA 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

AbstractLet 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

AbstractGiven 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

AbstractA 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

AbstractA 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

AbstractWe 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

AbstractTwo 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

AbstractLet 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

AbstractThe 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

AbstractLet 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

AbstractIn 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

AbstractThe 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

AbstractConsider 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

AbstractLet 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

AbstractWe 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

AbstractJames ProppThe 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

AbstractThe 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

AbstractMallows 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

AbstractWe 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.
Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
Authors: Gutin G. 
Published: May 2007

AbstractA 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

AbstractA λ‐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

AbstractNematode 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

AbstractAn 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

AbstractIn 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

AbstractThe 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

AbstractRaman 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

AbstractBackgroundGallbladder 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.MethodsThe 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.ResultsThere 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).ConclusionThe 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.