bluuebunny/crossref_metadata_2025_split huggingface dataset:
Sparse color‐critical graphs and hypergraphs with no short cycles
Authors: Abbott H. L. , Zhou B. , Hare D. R. 
Published: June 2007

AbstractWe give constructions of color‐critical graphs and hypergraphs with no short cycles and with relatively few edges. In particular, we show that, for each n ≧ 3, the smallest number of edges in a 3‐critical triangle‐free n‐graph (hypergraph) with m vertices is m + o(m) as m → ∞. Also, for each r ≧ 4, there exists an r‐critical triangle‐free 2‐graph (graph) with m vertices and at most (r − (7/3))m + o(m) edges. Weaker results are obtained for the existence of r‐critical graphs containing no cycle of length at most / > 3.
Local edge colorings that are global
Authors: Clapsadle R. A. , Schelp R. H. 
Published: June 2007

AbstractA local (H, k)‐coloring of Kn is a coloring of its edges in which each of its subgraphs isomorphic to H is colored by at most k colors. A necessary condition on H (conjectured to be sufficient) is found such that each local (H, k)‐coloring is a k‐coloring. Furthermore, necessary and sufficient conditions are given for each local (H, k)‐coloring to be a coloring by a bounded number of colors.
Set domination in graphs
Authors: Sampathkumar E. , Latha L. Pushpa 
Published: June 2007

AbstractLet G = (V, E) be a connected graph. A set D ⊂ V is a set‐dominating set (sd‐set) if for every set T ⊂ V − D, there exists a nonempty set S ⊂ D such that the subgraph 〈S ∪ T〉 induced by S ∪ T is connected. The set‐domination number γs(G) of G is the minimum cardinality of a sd‐set. In this paper we develop properties of this new parameter and relate it to some other known domination parameters.
Local and global average degree in graphs and multigraphs
Authors: Bertram E. , Erds P. , Horák P. , Širáň J. , Tuza Z. S. 
Published: June 2007

AbstractA vertex v of a graph G is called groupie if the average degree tv of all neighbors of v in G is not smaller than the average degree tG of G. Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the function f(n) = max minv (tv/tG), where the maximum ranges over all simple graphs on n vertices, and prove that f(n) = 1/42n + o(1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degree tv is constant.
Neighborhood unions and the cycle cover number of a graph
Authors: Chen Guantao , Gould Ronald J. , Jacobson Michael S. , Schelp Richard H. 
Published: June 2007

AbstractFor several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a bound on the smallest number of cycles in G containing all the vertices of G.We show that if for all x, y ≅ V(G), |N(x) ∩ N(y)| ≧ 2n/5 + 1, then V(G) is coverable by at most two cycles. Several related results and extensions to t cycles are also given.
On the orientation of meyniel graphs
Authors: Blidia Mostaffa , Duchet Pierre , Maffray Frédéric 
Published: June 2007

AbstractA kernel of a directed graph is a set of vertices K that is both absorbant and independent (i.e., every vertex not in K is the origin of an arc whose extremity is in K, and no arc of the graph has both endpoints in K). In 1983, Meyniel conjectured that any perfect graph, directed in such a way that every circuit of length three uses two reversible arcs, must have a kernel. This conjecture was proved for parity graphs. In this paper, we extend that result and prove that Meyniel's conjecture holds for all graphs in which every odd cycle has two chords.
Nonseparable graphs with a given number of cycles
Authors: Šćepanović Ranko , Ringel Gerhard , Marušič Dragan , Chia G. L. , Alspach Brian 
Published: June 2007

AbstractG. Ringel conjectured that for every positive integer n other than 2, 4, 5, 8, 9, and 16, there exists a nonseparable graph with n cycles. It is proved here that the conjecture is true even with the restriction to planar and hamiltonian graphs.
The 7/5‐conjecture strengthens itself
Authors: Kostochka A. V. 
Published: June 2007

AbstractThe following is proved: if every bridgeless graph G has a cycle cover of length at most 7/5|E(G)|, then every bridgeless graph G has a cycle cover of length at most 7/5|E(G)| such that any edge of G is covered once or twice. © 1995 John Wiley & Sons, Inc.
A class of planar well‐covered graphs with girth four
Authors: Pinter Michael R. 
Published: June 2007

AbstractA well‐covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1‐well‐covered graph was introduced by Staples in her 1975 dissertation: a well‐covered graph G is 1‐well‐covered if and only if G ‐ v is also well covered for every point v in G. Except for K2 and C5, every 1‐well‐covered graph contains triangles or 4‐cycles. We show that all planar 1‐well‐covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family. © 1995 John Wiley & Sons, Inc.
Total dominating functions in trees: Minimality and convexity
Authors: Cockayne E. J. , Mynhardt C. M. , Yu Bo 
Published: June 2007

AbstractA total dominating function (TDF) of a graph G = (V, E) is a function f: V ← [0, 1] such that for each v ϵ V, ΣuϵN(v) f(u) ≥ 1 (where N(v) denotes the set of neighbors of vertex v). Convex combinations of TDFs are also TDFs. However, convex combinations of minimal TDFs (i.e., MTDFs) are not necessarily minimal.In this paper we discuss the existence in trees of a universal MTDF (i.e., an MTDF whose convex combinations with any other MTDF are also minimal). © 1995 John Wiley & Sons, Inc.
Small graphs with chromatic number 5: A computer search
Authors: Jensen Tommy , Royle Gordon F. 
Published: June 2007

AbstractIn this article we give examples of a triangle‐free graph on 22 vertices with chromatic number 5 and a K4‐free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5‐critical graphs on 9 vertices are exhibited. © 1995 John Wiley & Sons, Inc.
Some results on the reconstruction problems. p‐claw‐free, chordal, and p4‐reducible graphs
Authors: Thatte Bhalchandra D. 
Published: June 2007

AbstractA claw is an induced subgraph isomorphic to K1,3. The claw‐point is the point of degree 3 in a claw. A graph is called p‐claw‐free when no p‐cycle has a claw‐point on it. It is proved that for p ≥ 4, p‐claw‐free graphs containting at least one chordless p‐cycle are edge reconstructible. It is also proved that chordal graphs are edge reconstructible. These two results together imply the edge reconstructibility of claw‐free graphs. A simple proof of vertex reconstructibility of P4‐reducible graphs is also presented. © 1995 John Wiley & Sons, Inc.
On the average genus of the random graph
Authors: Stahl Saul 
Published: June 2007

AbstractWe obtain an upper bound on the expected number of regions in the randomly chosen orientable embedding of a fixed graph. This bound is ised to show that the average genus of the random graph on v vertices is close to its maximum genus. More specifically, it is proven that the difference between these two parameters is bounded by a function that is linear in v. These bounds are obtained in the context of permutation—partition pairs. © 1996 John Wiley & Sons, Inc.
On point‐halfspace graphs
Authors: Scheinerman Edward R. , Trenk Ann N. , Ullman Daniel 
Published: June 2007

AbstractThe following definition is motivated by the study of circle orders and their connections to graphs. A graphs G is called a point‐halfspace graph (in Rk) provided one can assign to each vertex v ϵ (G) a point pv Rk and to each edge e ϵ E(G) a closed halfspace He ϵ Rk so that v is incident with e if and only if pv ϵ He. Let Hk denote the set of point‐halfspace graphs (in Rk).We give complete forbidden subgraph and structural characterizations of the classes Hk for every k. Surprisingly, these classes are closed under taking minors and we give forbidden minor characterizations as well. © 1996 John Wiley & Sons, Inc.
On Diagonally 10‐Coloring Plane Triangulations
Authors: Sanders Daniel P. , Zhao Yue 
Published: June 2007

AbstractThis article shows that the vertices of a plane triangulation may be colored with 10 colors such that every pair of vertices has different colors if they are either adjacent or diagonal, that is, that they are not adjacent but are adjacent to two faces which share an edge. This improves a result of Borodin, who showed that 11 colors were sufficient. © 1996 John Wiley & Sons, Inc.
A charcterization of 4‐edge‐connected eulerian graphs
Authors: Weidl Peter 
Published: June 2007

AbstractLet v be an arbitrary vertex of a 4‐edge‐connected Eulerian graph G. First we show the existence of a nonseparating cycle decompositiion of G with respect to v. With the help of this decomposition we are then able to construct 4 edge‐independent spanning trees with the common root v in the sam graph. We conclude that an Eulerian graph G is 4‐edge‐connected iff for every vertex r ϵ V (G) there exist 4 edge‐independent spanning trees with a common root r. © 1996 John Wiley & Sons, Inc.
On some properties of 4‐regular plane graphs
Authors: Horňá Mirko , Jendroľ Stanislav 
Published: June 2007

AbstractThe d‐distance face chromatic number of a connected plane graph is the minimum number of colors in such a coloring of its faces that whenever two distinct faces are at the distance at most d, they receive distinct colors. We estimate 1‐distance chromatic number for connected 4‐regular plane graphs. We show that 0‐distance face chromatic number of any connected multi‐3‐gonal 4‐regular plane graphs is 4. © 1995, John Wiley & Sons, Inc.
On the harmonious coloring of collections of graphs
Authors: Georges John P. 
Published: June 2007

AbstractThe hermonious coloring number of the graph G, HC(G), is the smallest number of colors needed to label the vertices of G such that adjacent vertices received different colors and no two edges are incident with the same color pair. In this paper, we investigate the HC‐number of collections of disjoint paths, cycles, complete graphs, and complete bipartite graphs. We determine exact expressions for the HC‐number of collections of paths and 4m‐cycles. © 1995, John Wiley & Sons, Inc.
Digraphs with the path‐merging property
Authors: Bang‐Jensen Jørgen 
Published: June 2007

AbstractIn this paper we study those digraphs D for which every pair of internally disjoint (X, Y)‐paths P1, P2 can be merged into one (X, Y)‐path P* such that V(P1) ∪ V(P2), for every choice of vertices X, Y ϵ V(D). We call this property the path‐merging property and we call a graph path‐mergeable if it has the path‐merging property. We show that each such digraph has a directed hamiltonian cycle whenever it can possibly have one, i.e., it is strong and the underlying graph has no cutvertex. We show that path‐mergeable digraphs can be recognized in polynomial time and we give examples of large classes of such digraphs which are not contained in any previously studied class of digraphs. We also discuss which undirected graphs have path‐mergeable digraph orientations. © 1995, John Wiley & Sons, Inc.
Fragments in kcritical n‐connected graphs
Authors: Jianji Su 
Published: June 2007

AbstractMadar conjectured that every k‐critical n‐connected non‐complete graph G has (2k + 2) pairwise disjoint fragments. We show that Mader's conjecture holds if the order of G is greater than (k + 2)n. From this, it implies that two other conjectures on k‐critical n‐connected graphs posed by Entringer, Slater, and Mader also hold if the cardinality of the graphs is large. © 1995 John Wiley & Sons, Inc.
Computing the orientable genus of projective graphs
Authors: Fiedler J. R. , Huneke J. P. , Richter R. B. , Robertson N. 
Published: June 2007

AbstractThe orientable genus is determined for any graph that embeds into the projective plane, Σ, to be essentially half of the representativity of any embedding into Σ. In addition, a structure is given for any 3‐connected projective planar graph as the union of a spanning planar graph and a variation of a Möbius Ladder. © 1995 John Wiley & Sons, Inc.
On Tutt's Characterization of graphic matroids—a graphic proof
Authors: Gerards A. M. H. 
Published: June 2007

AbstractIn this paper we present a relatively simple proof of Tutt's characterization of graphic matroids. The proof uses the notion of ‘signed graph’ and it is ‘graphic’ in the sense that it can be presented almost entirely by drawing (signed) graphs. © 1995 John Wiley & Sons, Inc.
Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
Authors: Hell Pavon , Huang Jing 
Published: June 2007

AbstractWe introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila‐Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. © 1995 John Wiley & Sons, Inc.
The fractional chromatic number of infinite graphs
Authors: Leader Imre 
Published: June 2007

AbstractThe fractional chromatic number of a graph G is the infimum of the total weight that can be assigned to the independent sets of G in such a way that, for each vertex v of G, the sum of the weights of the independent sets containing v is at least 1.In this note we give a graph a graph whose fractional chromatic number is strictly greater than the supremum of the fractional chromatic numbers of its finite subgraphs. This answers a question of Zhu. We also give some grphs for which the fractional chromatic number is not attined, answering another of Zhu. © 1995 John Wiley & Sons, Inc.
Degree Sums and Covering Cycles
Authors: Enomoto Hikoe , Kaneko Atsushi , Kouider Mekkia , Tuza Zsolt 
Published: June 2007

AbstractIt is shown that if in a simple graph G of order n the sum of degrees of any three pairwise non‐adjacent vertices is at least n, then there are two cycles (or one cycle and an edge or a vertex) of GF that contain all the vertices. © 1995 John Wiley & Sons, Inc.
On homomorphisms to acyclic local tournaments
Authors: Hell Pavol , Zhou Huishan , Zhu Xuding 
Published: June 2007

AbstractA homomorphism of a digraph to another digraph is an edgepreserving vertex mapping. A local tournament is a digraph in which the inset as well as the outset of each vertex induces a tournament. Thus acyclic local tournaments generalize both directed paths and transitive tournaments. In both these cases there is a simple characterization of homomorphic preimages. Namely, if H is a directed path, or a transitive tournament, then G admits a homomorphism to H if and only if each oriented path which admits a homomorphism to G also admits a homomorphism to H. We prove that this result holds for all acyclic local tournaments. © 1995 John Wiley & Sons, Inc.
Hamilton decompositions of some line graphs
Authors: Pike David A. 
Published: June 2007

AbstractThe main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that if G is a bipartite (2k + 1)‐regular graph that is Hamilton decomposable, then the line graph, L(G), of G is also Hamilton decomposable. A similar result is obtained for 5‐regular graphs, thus providing further evidence to support Bermond's conjecture. © 1995 John Wiley & Sons, Inc.
Structure analysis of triterpene saponins in Polygala tenuifolia by electrospray ionization ion trap multiple‐stage mass spectrometry
Authors: Liu Jiangyun , Yang Xuedong , He Jiuming , Xia Min , Xu Lizhen , Yang Shilin 
Published: June 2007

AbstractEighteen different triterpene saponins isolated from Polygala tenuifolia were investigated by electrospray ionization ion trap multiple‐stage mass spectrometry (ESI‐ITMSn) in positive and negative ion modes. MS1‐MS3/MS4 spectra of the both modes were analyzed, and they all gave fragments in line and shared common fragmentation patterns. Key fragments from MSn spectra of both the modes and their proposed fragmentation pathways were constructed with examples illustrated for the formation of characteristic fragments in the saponins. Two special fragmentation patterns were proposed: (1) the formation of fragments by cleavage of CH2O from Δ12‐14α‐CH2OH of the oleanene‐type saponin aglycone in both positive and negative MSn (n ≥ 2) modes; (2) the occurrence of fragments by cleavage of CO2 and 3‐glucose as the characteristic structure feature of 23‐COOH at the oleanene‐type saponin aglycones coupled with 3‐Glc substitutes in the negative MSn (n ≥ 2) modes. Peak intensities in MSn spectra were also correlated with structural features and fragmentation preferences of the investigated saponins, which are discussed in detail. In general, fragments formed predominantly by cleavages of glycosidic bonds in the positive mode, while selective cleavages of acyl bonds preceded that of glycosidic bonds in negative MSn (n ≥ 2) mode, both of which could well be applied to the structural analysis of these saponins. Interpretation of MSn spectra presented here provided diagnostic key fragment ions important for the structural elucidation of saponins in P.tenuifolia. Copyright © 2007 John Wiley & Sons, Ltd.
Characteristics of sleep disturbances in Japanese patients with Parkinson's disease. A study using Parkinson's disease sleep scale
Authors: Suzuki Keisuke , Okuma Yasuyuki , Hattori Nobutaka , Kamei Satoshi , Yoshii Fumihito , Utsumi Hiroya , Iwasaki Yasuo , Iijima Mutsumi , Miyamoto Tomoyuki , Miyamoto Masayuki , Hirata Koichi 
Published: June 2007

AbstractThe present multicenter cross‐sectional study was performed using semistructured questionnaires to determine the contributing factors of sleep disturbances in Japanese patients with Parkinson's disease (PD). We used the Parkinson's disease sleep scale (PDSS, Japanese version). All data were obtained by means of interviewed questionnaire and physical examination by neurologists. The study was carried out between April 2005 and December 2005 at eight university hospitals and affiliated facilities in the Kanto area of Japan. A total of 188 (85 men and 103 women) PD patients and 144 controls (64 men and 80 women) were included. Stepwise regression analysis identified complications of treatment, depression, age, and disease duration as significant risk factors of sleep disturbances in PD. Significant differences in total PDSS score were observed between Hoehn & Yahr (H&Y) Stages 1 and 4, between H&Y Stages 2 and 4, and between H&Y stages 3 and 4 (Bonferroni test). The results of this survey suggested that complications due to treatment (dyskinesia, wearing off, on–off), depressive state, and disease stage are significant determinants of sleep disorders in Japanese patients with PD. We speculate that the reduction of neurotransmitters involved in the sleep–wakefulness mechanism and degeneration of neurons progress together in parallel with deterioration of motor function. © 2006 Movement Disorder Society
An open trial of levetiracetam for segmental and generalized dystonia
Authors: Hering Sascha , Wenning Gregor K. , Seppi Klaus , Poewe Werner , Mueller Joerg 
Published: June 2007

AbstractLocal botulinum toxin injections represent the treatment of choice for most patients with focal dystonia. However, patients with segmental or generalized forms require additional pharmacologic treatment which is often ineffective or limited by intolerable side‐effects. An animal study and three case reports suggested antidystonic effects of levetiracetam, a pyrrolidone derivate, whereas a recent open‐label study found no improvement in 10 patients with primary idiopathic cervical dystonia. We studied the efficacy of levetiracetam in a daily dose of 3000 mg in 10 consecutive patients with otherwise therapy refractory segmental or generalized dystonia. At 4‐week follow‐up, none of the patients showed improvement of dystonia, mild side‐effects were observed in 3 patients. © 2007 Movement Disorder Society
The ST. Louis Recall Effort And Its Aftermath
Authors: Budenz Louis F. 
Published: June 2007

AbstractSt. Louis has just gone through a valuable municipal experience in the effort to recall Mayor Henry W. Kiel for his mill tax‐franchise deal with the United railways company. It furnishes an interesting sequel to the developments in the street railway situation outlined by the same author in the “National Municipal Review” for November, 1918.
Transfusional iron burden and liver toxicity after bone marrow transplantation for acute myelogenous leukemia and hemoglobinopathies
Authors: Jastaniah Wasil , Harmatz Paul , Pakbaz Zahra , Fischer Roland , Vichinsky Elliott , Walters Mark C. 
Published: June 2007

AbstractBackgroundWhile it is appropriate to treat transfusional iron overload to limit end‐organ injury after bone marrow transplantation (BMT) for β‐thalassemia major (TM), this approach after BMT for sickle cell disease (SCD) and hematological malignancies has not been studied.ProcedureFifteen children with SCD (n = 4), TM (n = 6), or acute myelogenous leukemia (AML, n = 5) underwent HLA‐identical sibling BMT between 2000 and 2003. Prospective evaluations of iron biomarkers were performed and the three groups were compared.ResultsThe pre‐BMT duration and volume of RBC transfusions varied among the three groups, but baseline ferritin and liver iron concentration (LIC) were similar. In contrast, liver histology differed. Liver inflammation was present in four TM patients and portal fibrosis was observed in five TM and one SCD patient. Hepatic veno‐occlusive disease (VOD) developed in 5 of 15 patients. VOD was not associated with age, ferritin, ALT, or transfusions, but an association with liver inflammation and elevated LIC was suggested. Phlebotomy was performed in five patients after BMT. Changes in LIC were minimal in non‐phlebotomized patients (P = 0.02).ConclusionIron biomarkers demonstrated significant iron overload before BMT in patients with malignant and non‐malignant disorders. However, iron overload was associated with liver inflammation and VOD primarily in TM patients. The clinical significance of iron overload in patients after BMT remains uncertain, but this is the first study to suggest that VOD may be associated with transfusional iron burden. Pediatr Blood Cancer 2008;50:319–324. © 2007 Wiley‐Liss, Inc.