bluuebunny/crossref_metadata_2025_split huggingface dataset:
Forests of label‐increasing trees
Authors: Riordan John 
Published: May 2007

AbstractLabel‐increasing trees are fully labeled rooted trees with the restriction that the labels are in increasing order on every path from the root; the best known example is the binary case—no tree with more than two branches at the root, or internal vertices of degree greater than three—extensively examined by Foata and Schutzenberger in A Survey of Combinatorial Theory. The forests without branching restrictions are enumerated by number of trees by Fn(x) = x(x + 1)…(x + n − 1), n >1 (F0(x) = 1), whose equivalent: Fn(x) = Yn(xT1,…, xTn), Fn(1)= Tn + 1 = n!, is readily adapted to branching restriction.
On some subclasses of well‐covered graphs
Authors: Staples Jo Ann W. 
Published: May 2007

AbstractA set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well‐covered graphs are classified by the Wn property: For a positive integer n, a graph G belongs to class Wn if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of Wn graphs containing arbitrarily large independent sets. A characterization of Wn graphs in terms of well‐covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in Wn graphs.
𝒢‐constructibility of planar graphs
Authors: Mynhardt C. M. , Broere I. 
Published: May 2007

AbstractIn this paper, the concept of the 𝒢‐constructibility of graphs is introduced and investigated with particular reference to planar graphs. It is conjectured that the planar graphs are minimally N‐constructible, where N is a finite set of graphs and an infinite set 𝒢 is obtained such that the planar graphs are also minimally 𝒢‐constructible. Finally, some properties of the set of all N‐constructible graphs are discussed and compared with the corresponding properties of planar graphs.
The genus of the 2‐amalgamations of graphs
Authors: Decker R. W. , Glover H. H. , Huneke J. P. 
Published: May 2007

AbstractA graph G is called the 2‐amalgamation of subgraphs G1 and G2 if G = G1 ∪ G2 and G1 ∩ G2 = {x, y}, 2 distinct points. in this case we write G = G1∪{x, y} G2. in this paper we show that the orientable genus, γ(G), satisfies the inequalities γ(G1) + γ(G2) − 1 ≤ γ(G1 ∪{x, y} G2) ≤ γ(G1) + γ(G2) + 1 and that this is the best possible result, i. e., the resulting three values for γ(G1 ∪{x, y} G2) which are possible can actually be realized by appropriate choices for G1 and G2.
On the theory of the matching polynomial
Authors: Godsil C. D. , Gutman I. 
Published: May 2007

AbstractIn this paper we report on the properties of the matching polynomial α(G) of a graph G. We present a number of recursion formulas for α(G), from which it follows that many families of orthogonal polynomials arise as matching polynomials of suitable families of graphs. We consider the relation between the matching and characteristic polynomials of a graph. Finally, we consider results which provide information on the zeros of α(G).
Pseudosimilar vertices in a graph
Authors: Kimble Robert J. , Schwenk Allen J. , Stockmeyer Paul K. 
Published: May 2007

AbstractDissimilar vertices whose removal leaves isomorphic subgraphs are called pseudosimilar. We construct infinite families of graphs having identity automorphism group, yet every vertex is pseudosimilar to some other vertex. Potential impact on the Reconstruction Conjecture is considered. We also construct, for each n, graphs containing a subset of n vertices which are mutually pseudosimilar. the analogous problem for mutually pseudosimilar edges is introduced.
On the existence of a specified cycle in digraphs with constraints on degrees
Authors: Benhocine Abdelhamid 
Published: May 2007

AbstractWe prove that Woodall's and Ghouila‐Houri's conditions on degrees which ensure that a digraph is Hamiltonian, also ensure that it contains the analog of a directed Hamiltonian cycle but with one edge pointing the wrong way; that is, it contains two vertices that are connected in the same direction by both an edge and a Hamiltonian path.
Isomorphic factorizations VII. Regular graphs and tournaments
Authors: Wormald N. C. 
Published: May 2007

AbstractIt is shown using enumeration results that for r > 2t, almost all labeled r‐regular graphs cannot be factorized into t ⩾ 2 isomorphic subgraphs. However, no examples of such nonfactorizable graphs are known which satisfy the obvious divisibility condition that the number of edges is divisible by t. Similar observations hold for regular tournaments (t ⩾ 2} and for r‐regular digraphs (r > t ⩾ 2).
On superperfect noncomparability graphs
Authors: Andreae Thomas 
Published: May 2007

AbstractThe class of superperfect graphs, which was previously studied by A. J. Hoffman, E. L. Johnson, and M. C. Golumbic, is a proper subclass of the class of perfect graphs; further, it properly contains the class of comparability graphs. In his book, Golumbic proves that, for split graphs, G is a comparability graph if and only if G is superperfect. Moreover, the fact that split graphs are exactly those graphs which are both triangulated and cotriangulated motivated Golumbic to ask if it is true or false that, for triangulated (or cotriangulated) graphs, G is a comparability graph if and only if G is superperfect. In the present paper, we determine those members of Gallai's list of minimal noncomparability graphs which are superperfect and, as a consequence, we find that the answer to the above question is “false” for triangulated and “true” for cotriangulated graphs.
On partitioning the edges of graphs into connected subgraphs
Authors: Jünger M. , Reinelt G. , Pulleyblank W. R. 
Published: May 2007

AbstractFor any positive integer s, an s‐partition of a graph G = (V, E) is a partition of E into E1 ∪ E2 ∪…︁ ∪ Ek, where ∣Ei∣ = s for 1 ≤ i ≤ k − 1 and 1 ≤ ∣Ek∣ ≤ s and each Ei induces a connected subgraph of G. We prove

If G is connected, then there exists a 2‐partition, but not necessarily a 3‐partition;
If G is 2‐edge connected, then there exists a 3‐partition, but not necessarily a 4‐partition;
If G is 3‐edge connected, then there exists a 4‐partition;
If G is 4‐edge connected, then there exists an s‐partition for all s.
Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
Authors: Cowen L. J. , Cowen R. H. , Woodall D. R. 
Published: May 2007

AbstractWe call a graph (m, k)‐colorable if its vertices can be colored with m colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. For the class of planar graphs, and the class of outerplanar graphs, we determine all pairs (m, k) such that every graph in the class is (m, k)‐colorable. We include an elementary proof (not assuming the truth of the four‐color theorem) that every planar graph is (4, 1)‐colorable. Finally, we prove that, for each compact surface S, there is an integer k = k(S) such that every graph in S can be (4, k)‐colored; we conjecture that 4 can be replaced by 3 in this statement.
A class of self‐complementary vertex‐transitive digraphs
Authors: Chia Gek‐Ling , Lim Chong‐Keang 
Published: May 2007

AbstractWe characterize the class of self‐complementary vertex‐transitive digraphs on a prime number p of vertices. Using this, we enumerate (i) self‐complementary strongly vertex‐transitive digraphs on p vertices, (ii) self‐complementary vertex‐transitive digraphs on p vertices, (iii) self‐complementary vertex‐transitive graphs on p vertices. Finally it is shown that every self‐complementary vertex‐transitive digraph on p vertices is either a tournament or a graph.
A degree condition for the circumference of a graph
Authors: Dean Nathaniel , Fraisse Pierre 
Published: May 2007

AbstractWe present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2‐connected graph with vertices x1,…,xn and edge set E that satisfies the property that, for any two integers j and k with j < k, xjxk ∉ E, d(xi) ⩽ j and d(xk) ⩽ K ‐ 1, we have (1) d(xi) + d(xk ⩾ m if j + k ⩾ n and (2) if j + k < n, either m ⩾ n or d(xj) + d(xk) ⩾ min(K + 1,m). Then c(G) ⩾ min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.
Tight bounds on the chromatic sum of a connected graph
Authors: Thomassen Carsten , Erdös Paul , Alavi Yousef , Malde Paresh J. , Schwenk Allen J. 
Published: May 2007

AbstractThe chromatic sum of a graph is introduced in the dissertation of Ewa Kubicka. It is the smallest possible total among all proper colorings of G using natural numbers. In this article we determine tight bounds on the chromatic sum of a connected graph with e edges.
Alternating cycles in edge‐colored graphs
Authors: Whitehead Carol 
Published: May 2007

AbstractWe show that the edges of a 2‐connected graph can be partitioned into two color classes so that every vertex is incident with edges of each color and every alternating cycle passes through a single edge. We also show that the edges of a simple graph with minimum vertex degree δ ≫ 2 can be partitioned into three color classes so that every vertex is incident with edges in exactly two colors and no cycle is alternating.
Double cycle covers and the petersen graph
Authors: Catlin Paul A. 
Published: May 2007

AbstractLet O(G) denote the set of odd‐degree vertices of a graph G. Let t ϵ N and let 𝒮t denote the family of graphs G whose edge set has a partition.E(g) = E1 U E2 U … U Etsuch that O(G) = O(G[Ei]) (1 ⩽ i ⩽ t). This partition is associated with a double cycle cover of G. We show that if a graph G is at most 5 edges short of being 4‐edge‐connected, then exactly one of these holds: G ϵ 𝒮3, G has at least one cut‐edge, or G is contractible to the Petersen graph. We also improve a sufficient condition of Jaeger for G ϵ 𝒮2p+1(p ϵ N).
On critically connected digraphs
Authors: Mader W. 
Published: May 2007

AbstractA digraph is called critically connected if it is connected, but the deletion of any vertex destroys the connectivity. We prove that every critically connected finite digraph has at least two vertices of outdegree one. As an application, we show that for n ≧ 2, there is no n‐connected, non‐complete, finite digraph such that the deletion of any n vertices results in a disconnected digraph.
Automorphism groups of pictures
Authors: Behrendt Gerhard 
Published: May 2007

AbstractA picture is a simple graph together with an edge‐coloring, such that each vertex is incident with exactly one edge of each color. An automorphism of a picture is a graph automorphism that preserves the colors of the edges. We show that every group is isomorphic to the full automorphism group of a picture, and prove that a group is isomorphic to a vertex‐transitive subgroup of the automorphism group of a picture if and only if it can be generated by involutions.
3‐edge‐connected embeddings have few singular edges
Authors: Bender Edward A. , Richmond L. Bruce 
Published: May 2007

AbstractWe show that a 3‐edge‐connected graph embedded in a surface of Euler characteristic χ has at most 3 – 3χ singular edges, except in the projective plane, where it has at most one singular edge, and the sphere, where it has none. This bound is best possible for all surfaces.
Generalized exponents of primitive directed graphs
Authors: Brualdi Richard A. , Liu Bolian 
Published: May 2007

AbstractThe exponent of a primitive digraph is the smallest integer t such that for each ordered pair of (not necessarily distinct) vertices x and y there is a path of length t from x to y. There is considerable information known about bounds on exponents and those numbers that can be exponents of primitive digraphs with n vertices. We introduce some new parameters related to the exponent and obtain bounds on these parameters.
Steiner centers in graphs
Authors: Oellermann Ortrud R. , Tian Songlin 
Published: May 2007

AbstractThe Steiner distance of a set S of vertices in a connected graph G is the minimum size among all connected subgraphs of G containing S. For n ≥ 2, the n‐eccentricity en(ν) of a vertex ν of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contains ν. The n‐diameter of G is the maximum n‐eccentricity among the vertices of G while the n‐radius of G is the minimum n‐eccentricity. The n‐center of G is the subgraph induced by those vertices of G having minimum n‐eccentricity. It is shown that every graph is the n‐center of some graph. Several results on the n‐center of a tree are established. In particular, it is shown that the n‐center of a tree is a tree and those trees that are n‐centers of trees are characterized.
Bounds for rectilinear crossing numbers
Authors: Bienstock Daniel , Dean Nathaniel 
Published: May 2007

AbstractA rectilinear drawing of a graph is one where each edge is drawn as a straight‐line segment, and the rectilinear crossing number of a graph is the minimum number of crossings over all rectilinear drawings. We describe, for every integer k ≥ 4, a class of graphs of crossing number k, but unbounded rectilinear crossing number. This is best possible since the rectilinear crossing number is equal to the crossing number whenever the latter is at most 3. Further, if we consider drawings where each edge is drawn as a polygonal line segment with at most one break point, then the resulting crossing number is at most quadratic in the regular crossing number. © 1993 John Wiley & Sons, Inc.
Rainbow coloring the cube
Authors: Faudree R. J. , Gyárfás A. , Lesniak L. , Schelp R. H. 
Published: May 2007

AbstractWe prove that for d ≥ 4, d ≠ 5, the edges of the d‐dimensional cube can be colored by d colors so that all quadrangles have four distinct colors. © 1993 John Wiley & Sons, Inc.
Extremal graphs without three‐cycles or four‐cycles
Authors: Garnick David K. , Kwong Y. H. Harris , Lazebnik Felix 
Published: May 2007

AbstractWe derive bounds for f(v), the maximum number of edges in a graph on v vertices that contains neither three‐cycles nor four‐cycles. Also, we give the exact value of f(v) for all v up to 24 and constructive lower bounds for all v up to 200. © 1993 John Wiley & Sons, Inc.
Generalized fibonacci cubes are mostly hamiltonian
Authors: Liu Jenshiuh , Hsu Wen‐Jing , Chung Moon Jung 
Published: May 2007

AbstractTheHamiltonian problemis to determine whether a graph contains a spanning (Hamiltonian) path or cycle. Here we study the Hamiltonian problem for thegeneralized Fibonacci cubes, which are a new family of graphs that have applications in interconnection topologies [J. Liuand W.‐J. Hsu, „Distributed Algorithms for Shortest‐Path, Deadlock‐Free Routing and Broadcasting in a Class of Interconnection Topologies,”︁ International Parallel Processing Symposium (1992)]. We show that each member of this family contains a Hamiltonian path. Furthermore, we also characterize the members of this family that contain a Hamiltonian cycle.
The irredundant ramsey number s(3, 7)
Authors: Chen Guantao , Rousseau Cecil C. 
Published: May 2007

AbstractThe irredundant Ramsey number s(m, n) is the smallest p such that for every graph G with p vertices, either G contains an n‐element irredundant set or its complement G contains an m‐element irredundant set. Cockayne, Hattingh, and Mynhardt have given a computer‐assisted proof that s(3, 7) = 18. The purpose of this paper is to give a self‐contained proof of this result. © 1995 John Wiley & Sons, Inc.
The edge reconstruction number of a disconnected graph
Authors: Molina Robert 
Published: May 2007

AbstractThe edge reconstruction number of a graph G, RN(G), is the minimum number of edge deleted subgraphs required to determine G up to isomorphism. We prove the following results for a disconnected graph G with at least two nontrivial components. If G has a pair of nontrivial nonisomorphic components then RN(G) ≤ 3. If G has a pair of nontrivial nonisomorphic components, is not a forest, and contains a nontrivial component other than K3 or K1,3 then RN(G) ≤ 2. Finally, if all nontrivial components of G are isomorphic to a graph with k edges, then RN(G) ≤ k + 2. The edge reconstruction results in this paper are similar to the vertex reconstruction results stated by Myrvold (“The Ally‐Reconstruction Number of a Disconnected Graph,” Ars Combinatoria, Vol. 28 [1989] pp. 123‐127), but a significant difference is that the edge reconstruction number of a disconnected graph is often two, while the vertex reconstruction number of a graph is always three or more. © 1995 John Wiley & Sons, Inc.
A new proof of the 6 color theorem
Authors: Borodin Oleg V. 
Published: May 2007

AbstractIn 1965 Ringel raised a 6 color problem for graphs that can be stated in at least three different forms. In particular, is it possible to color the vertices and faces of every plane graph with 6 colors so that any two adjacent or incident elements are colored differently? This 6 color problem was solved in 1984 by the present author; the proof used about 35 reducible configurations. A shorter new proof is given here using only half as many of reducible configurations. © 1995 John Wiley & Sons, Inc.
Flexibility along the neck of the ostrich (Struthio camelus) and consequences for the reconstruction of dinosaurs with extreme neck length
Authors: Dzemski Gordon , Christian Andreas 
Published: May 2007

AbstractThe gross morphology and the flexibility along the neck of the ostrich (Struthio camelus) were examined using fresh tissue as well as neck skeletons. The results of the morphologic studies were compared with results from observations of living ostriches. The investigation was focused on differences in the morphology and the function between different sections of the neck. Additionally, the function of major dorsal neck ligaments was examined, including measurements of force‐strain‐relations. Comparative studies of giraffes (Giraffa camelopardalis) and camels (Camelus bactrianus) were conducted to find relations between the flexibility along the neck and the general feeding strategy. The examinations revealed that the neck of the ostrich can be divided into four sections with different functions. The first is the atlas‐axis‐complex which is responsible for torsion. The adjacent cranial section of the neck is flexible in dorsoventral and lateral directions but this part of the neck is usually kept straight at rest and during feeding. Dorsoventral flexibility is highest in the middle section of the neck, whereas the base of the neck is primarily used for lateral excursions of the neck. For giraffes and camels, the posture and utilization of the neck are also reflected in the flexibility of the neck. For all three species, it is possible to reconstruct the pattern of flexibility of the neck by using the neck skeletons alone. Therefore, it appears reasonable to reconstruct the neck utilization and the feeding strategies of dinosaurs with long necks by deriving the flexibility of the neck from preserved vertebrae. For Diplodocus carnegii the neck posture and the feeding strategy were reconstructed. Two neck regions, one around the 9th neck vertebra and the second at the base of the neck, indicate that Diplodocus, like the ostrich, adopted different neck postures. The neck was probably kept very low during feeding. During interruptions of the feeding, e.g., in an alert, the head could have been lifted in an economic way by raising the cranial section of the neck. During standing and locomotion the head was probably located well above the shoulders. J. Morphol., 2007. © 2007 Wiley‐Liss, Inc.
Validation of direct injection electrospray LC‐MS/MS for confirmation of opiates in urine drug testing
Authors: Gustavsson E. , Andersson M. , Stephanson N. , Beck O. 
Published: May 2007

AbstractA method based on the direct injection of diluted urine for the identification and quantification of morphine, morphine‐3‐glucuronide, morphine‐6‐glucuronide, codeine, codeine‐6‐glucuronide, ethylmorphine, ethylmorphine‐6‐glucuronide and 6‐acetylmorphine (6AM) in human urine by electrospray ionisation liquid chromatography‐tandem mass spectrometry was validated for use as a confirmation procedure in urine drug testing. Four deuterium labelled analogues were used as internal standards: morphine‐3‐glucuronide‐D3, morphine‐D3, codeine‐D3 and 6AM‐D3. Twenty microlitre aliquots of urine were mixed with 80 μl of the internal standard solution in autosampler vials and 10 μl was injected. The chromatographic system consisted of a 2.0 × 100 mm C18 column and the gradient elution buffers used acetonitrile and 25 mmol/l formic acid. Two product ions produced from the protonated molecular ions were monitored in the selected reaction monitoring mode. The intra‐ and inter‐assay variability (coefficient of variation) was below 10% at higher levels for all analytes, but at the reporting limits the variation was above 20% for 6AM, morphine‐3‐glucuronide and codeine‐6‐glucuronide. Ion suppression occurred early after injection but did not affect the identification and quantification of the analytes in authentic samples. The method was further validated by comparison with a reference gas chromatographic‐mass spectrometric method using authentic urine samples. The two methods agreed almost completely (99%) regarding the identified analytes, but for the quantitative results there were slightly lower levels when measuring glucuronides directly as compared to total determination after hydrolysis by gas chromatography‐mass spectrometry.We conclude that the presented liquid chromatographic‐tandem mass spectrometric method is robust and reliable, and suitable for use as a confirmation method in urine drug testing for opiates
Copyright © 2007 John Wiley & Sons, Ltd.
Electrospray ionization‐multistage tandem mass spectrometry of complex multitin organometallic compounds
Authors: Jirásko Robert , Holčapek Michal , Kolářová Lenka , Basu Baul Tushar S. 
Published: May 2007

AbstractThe series of 14 complex organotin(IV) compounds containing many tin atoms and noncovalent bonds in the structure was characterized by electrospray ionization multistage tandem mass spectrometry (ESI‐MSn). The mass spectra were measured in both polarity modes to obtain complementary structural information. The characteristic pattern of ten natural tin isotopes allowed the determination of the number of tin atoms in the molecular adducts and fragment ions by comparing theoretical and experimental isotopic distributions. Positive ion ESI spectra show unusual adduct formation depending on the type of organic solvent used for the direct infusion analysis owing to the ion–molecule reactions in the ion source. On the basis of the detailed spectral interpretation of organotin(IV) compounds, the fragmentation patterns of multitin organometallic compounds have been proposed. Noncovalent bonds in polymeric complexes are fragmented first, which is then followed by characteristic neutral losses in monomeric units. Copyright © 2007 John Wiley & Sons, Ltd.