bluuebunny/crossref_metadata_2025 huggingface dataset:
Quantitative polymerase chain reaction as a reliable method to determine functional lentiviral titer after ex vivo gene transfer in human mesenchymal stem cells
Authors: Böcker Wolfgang , Rossmann Oliver , Docheva Denitsa , Malterer Georg , Mutschler Wolf , Schieker Matthias
Published: May 2007

Background

Human mesenchymal stem cells (hMSCs) are a promising target for ex vivo gene therapy and lentiviruses are excellent gene transfer vehicles in hMSCs since they achieve high transduction rates with long‐term gene expression. Nevertheless, senescence of hMSCs may limit therapeutic applications due to time‐consuming cell selection and viral titration. Here, we describe a fast and reliable method to determine functional lentiviral titer by quantitative polymerase chain reaction (qPCR) after highly efficient ex vivo gene transfer in hMSCs.

Methods

Lentivirus production was tested with different types of packaging systems. Using p24 ELISA remaining viral particles were detected in the cell culture supernatant. The lentiviral gene transfer efficiency was quantified by FACS analysis. Lentiviral titers were determined by qPCR of expressed transgenes.

Results

Third‐generation self‐inactivating vectors showed highly efficient gene transfer in hMSCs. No viral antigen was detected in the cell culture supernatant after four media changes, suggesting the absence of infectious particles after 4 days. We observed a linear correlation between virus dilution and level of transgene expression by qPCR analysis, therefore allowing viral titering by quantification of transgene expression. Finally, we demonstrated that transduced hMSCs retained their stem cell character by differentiation towards adipogenic, osteogenic and chondrogenic lineages.

Conclusions

Quantification of transgene copy numbers by qPCR is a fast and reliable method to determine functional lentiviral titer after ex vivo gene transfer in hMSCs. Copyright © 2007 John Wiley & Sons, Ltd.
G‐CSF‐lentivirus administration in rats provided sustained elevated neutrophil counts and subsequent EPO‐lentivirus administration increased hematocrits
Authors: Brzezinski Margaret , Yanay Ofer , Waldron Lanaya , Barry Simon C. , Osborne William R. A.
Published: May 2007

Background

Towards gene therapy treatment of patients with neutropenia, characterized by neutrophil counts < 500 cells/µl, we investigated the ability of lentivirus vectors to provide sustained granulocyte colony‐stimulating factor (G‐CSF) delivery and to permit transgene expression from a second virus administration in a preclinical rat model.

Methods

Rats were injected intramuscularly (IM) with 24 × 106 and 9 × 106 infectious units (IU) of a VSV‐G‐pseudotyped self‐inactivating (SIN) lentivirus encoding rat G‐CSF cDNA and containing cPPT and PRE elements. To determine the effectiveness of a second virus administration treated rats and a naïve rat received erythropoietin (EPO)‐lentivirus IM. Rats were monitored for neutrophil and red blood cell production. Lentivirus antibodies were assayed by virus‐neutralizing assay and ELISA.

Results

High and low dose virus administration increased neutrophil counts to 5660 ± 930 cells/µl (mean ± SD) and 4010 ± 850 cells/µl, respectively, that were sustained for > 17 months and were significantly higher than controls counts of 1890 ± 570 cells/µl (p⩽0.0002). Rats treated with EPO‐virus produced significantly increased hematocrits (HCT) (63.1 ± 4.3% vs. 46.0 ± 3.2%, p < 0.0001) without effect on G‐CSF‐virus‐mediated neutrophil production. Antivirus antibodies were not detectable at serum dilutions ≥1:10 by virus neutralization or ELISA. Lymphocytes and platelets were not significantly different between control and treated animals (p > 0.1). Only genomic DNA from muscle at injection sites was positive for provirus suggesting lack of virus spread.

Conclusions

G‐CSF‐lentivirus administered IM provided elevated, sustained neutrophil counts that were unchanged by subsequent EPO‐lentivirus administration. Significantly increased hematocrits were obtained following EPO‐lentivirus delivery. These data support the treatment of patients with severe chronic neutropenia by dosed lentivirus delivery IM. Copyright © 2007 John Wiley & Sons, Ltd.
Some sufficient conditions for the existence of a 1‐factor
Authors: Nebeský Ladislav
Published: May 2007

The following theorem is proved: Let G be a graph of even order. Assume that there exists a connected spanning subgraph F of G such that for every set U of four vertices in G, if the subgraph of F induced by U is a star, then the subgraph of G induced by U is complete. Then G has a 1‐factor. The above theorem is derived from another sufficient condition for the existence of a 1‐factor, which is also proved in this paper (Lemma 1).
A new proof of menger's theorem
Authors: O'Neil Peter V.
Published: May 2007

A new proof of Menger's theorem is presented.
Counterexamples to two conjectures of Hilton
Authors: Fiorini S.
Published: May 2007

Counterexamples are presented to the following two conjectures of Hilton:

A graph which does not contain a spanning K1t is Vl‐critical if and only if it is VC‐critical.

If G is a class‐two graph which contains a spanning Pl‐critical subgraph H of the same chromatic index as G, then G is Vl‐critical.

The counterexample to the second conjecture also illustrates that a class‐two graph can have distinct Pl‐critical subgraphs.
The embeddings of a graph—A survey
Authors: Stahl Saul
Published: May 2007

Topological graph theory seeks to find answers to the question of how graphs map into surfaces. This paper surveys the information now available about the range of a graph, namely, the set of surfaces on which the graph can be “neatly” embedded. Several other closely related topics, such as irreducible graphs, coloring problems, and crossing numbers, are ignored. As is quite often the case with mathematical theories, this discipline developed in a rather haphazard manner. Many isolated results existed before the practitioners became aware of the fact that they were developing a theory. The turning point occurred in 1968, when Ringel and Youngs completed their proof of the Heawood conjecture. Their proof, in addition to settling an old unsolved problem, also reinforced the significance of the rotation systems. It is the author's belief that these rotation systems, together with the generalized embedding schemes can, and should, become the main tool in all investigations concerning the embeddings of a graph. This survey is written from that point of view. After defining the scope of the area surveyed, this paper proceeds to discuss the significance of the rotation systems and embedding schemes. Several theorems of a general nature are listed. Attention is then focused on the maximum and minimum genera of a graph. Discussion of the first of these is deferred to another survey article by R. Ringeisen to appear in a subsequent issue. The various methods developed by researchers in this area for determining the (minimum) genus are then described. This is followed by a listing of all the theoretical information that is available about the genus parameter. The paper includes two tables that exhibit most of the graphs with known genus.
The number of connected sparsely edged graphs. II. Smooth graphs and blocks
Authors: Wright E. M.
Published: May 2007

A smooth graph is a connected graph without endpoints; f(n, q) is the number of connected graphs, v(n, q) is the number of smooth graphs, and u(n, q) is the number of blocks on n labeled points and q edges: Wk, Vk, and Uk are the exponential generating functions of f(n, n + k), v(n, n + k), and u(n, n + k), respectively. For any k ⩾ 1, our reduction method shows that Vk can be deduced at once from Wk, which was found for successive k by the computer method described in our previous paper. Again the reduction method shows that Uk must be a sum of powers (mostly negative) of 1 ‐ X and, given this information, we develop a recurrence method well suited to calculate Uk for successive k. Exact formulas for v(n, n + k) and u(n, n + k) for general n follow at once.
On the connectivity of maximal planar graphs
Authors: Hakimi S. L. , Schmeichel E. F.
Published: May 2007

Let d1 ⩾ d2 ⩾ … ⩾ dp be the vertex degrees of a maximal planar graph G. Etourneau has shown that if d1 ⩽ 6 and dp = 5, then G is 5‐connected. We generalize Etourneau's result by giving sufficient conditions in terms of the vertex degrees for G to be dp ‐connected.
The smallest nontoroidal chiral maps
Authors: Wilson Steve
Published: May 2007

In this paper, we display those chiral maps which have fewest edges among those of genus greater than one. One of these is a branched covering of a regular map on the torus, and the other is its dual.
Characterization of maximum critically 2‐connected graphs
Authors: Entringer R. C.
Published: May 2007

A graph G is critically 2‐connected if G is 2‐connected but, for any point p of G, G — p is not 2‐connected. Critically 2‐connected graphs on n points that have the maximum number of lines are characterized and shown to be unique for n ⩾ 3, n ≠ 11.
Graphs with symmetric automorphism group
Authors: Wallis W. D. , Heinrich Katherine
Published: May 2007

We investigate the properties of graphs whose automorphism group is the symmetric group. In particular, we characterize graphs on less than 2n points with group Sn, and construct all graphs on n + 3 points with group Sn. Graphs with 2n or more points and group Sn are discussed briefly.
Survey of results on the maximum genus of a graph
Authors: Ringeisen Richard D.
Published: May 2007

Some of the early questions concerning the maximum genus of a graph have now been answered. In this paper we survey the progress made on such problems and present some recent results, outlining proofs for some of the major theorems.
Minimally 2‐edge connected graphs
Authors: Chaty G. , Chein M.
Published: May 2007

A constructive characterization of minimally 2‐edge connected graphs, similar to those of Dirac for minimally 2‐connected graphs is given.
1‐Factorizations of cartesian products of regular graphs
Authors: Kotzig Anton
Published: May 2007

Let G1, G2…, Gn be regular graphs and H be the Cartesian product of these graphs (H = G1 × G2 × … × Gn). The following will be proved: If the set {G1, G2…, Gn} has at leat one of the following properties: (*) for at leat one i ϵ {1, 2,…, n}, there exists a 1‐factorization of Gi or (**) there exists at least two numbers i and j such that 1 ≤ i < j ≤ n and both the Graphs Gi and Gj contain at least one 1‐factor, then there exists a 1‐factorization of H. Further results: Let F be a cycle of length greater than three and let G be an arbitrary cubic graph. Then there exists a 1‐factorization of the 5‐regular graph H = F × G. The last result shows that neither (*) nor (**) is a necessary condition for the existence of a 1‐factorization of a Cartesian product of regular graphs.
An intermediate value theorem for graphs with given automorphism group
Authors: Hell Pavol , Quintas Louis V.
Published: May 2007

For a positive integer n and a finite group G, let the symbols e(G, n) and E(G, n) denote, respectively, the smallest and the greatest number of lines among all n‐point graphs with automorphism group G. We say that the Intermediate Value Theorem (IVT) holds for G and n, if for each e satisfying e(G, n)≤e≤E(G, n), there exists an n‐point graph with group G and e lines. The main result of this paper states that for every group G the IVT holds for all sufficiently large n. We also prove that the IVT holds for the identity group and all n, and exhibit examples of groups for which the IVT fails to hold for small values of n.
Cochromatic Number and the Genus of a Graph
Authors: Straight H. Joseph
Published: May 2007

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each sbuset induces an empty or a complete subgraph of G. In this paper we introduce the problem of determining for a surface S, z(S), which is the maximum cochromatic number among all graphs G that embed in S. Some general bounds are obtained; for example, it is shown that if S is orientable of genus at least one, or if S is nonorientable of genus at least four, then z(S) is nonorientable of genus at least four, then z(S)≤χ(S). Here χ(S) denotes the chromatic number S. Exact results are obtained for the sphere, the Klein bottle, and for S. It is conjectured that z(S) is equal to the maximum n for which the graph Gn = K1 ∪ K2 ∪ … ∪ Kn embeds in S.
Voltage graph embeddings and the associated block designs
Authors: Garman Brian L.
Published: May 2007

The voltage graph construction of Gross (orientable case) and Stahl as well as Gross and Tucker (nonorientable case) is extended to the case where the base graph is embedded in a pseudosurface or a generalized pseudosurface. This theory is then applied to produce triangular embeddings of K4(n); they in turn yield an infinite class of partially balanced incomplete block designs.
On Line Graphs with Crossing Number 1
Authors: Kulli V. R. , Akka D. G. , Beineke L. W.
Published: May 2007

In this paper we deduce a necessary and sufficient condition for a line grah to have crossing number 1. In addition, we prove that the line graph of any nonplanar graph has crossing number greater than 2.
Further annotated bibliography on the isomorphism disease
Authors: Gati Georg
Published: May 2007

This annotated bibliography contains 32 papers on graph isomorphism not included in the bibliography of Read and Corneil, most of which discuss algorithms or their theoretical foundations. We include articles by Miller, Weisfeiler, and Whitney as well as algorithms by Johnson and Leighton, Schmidt and Druffel, Tinhofer, and Erdös and Babai.
On the construction of the self‐complementary graphs on 12 nodes
Authors: Kropar Marg , Read Ronald C.
Published: May 2007

We briefly describe how we compiled a catalog of all the 720 self‐complementary graphs on 12 nodes. In our first attempt at this compilation one graph was inadvertently omitted. The missing graph was subsequently found by making use of a theoretical formula due to Parthasarathy and Sridharan for counting self‐complementary graphs with given partitions.
Group labelings of graphs
Authors: Edelman Paul H. , Saks Michael
Published: May 2007

Given a graph Γ an abelian group G, and a labeling of the vertices of Γ with elements of G, necessary and sufficient conditions are stated for the existence of a labeling of the edges in which the label of each vertex equals the product of the labels of its incident edges. Such an edge labeling is called compatible. For vertex labelings satisfying these conditions, the set of compatible edge labelings is enumerated.
Spanning arborescences, ingraphs, and outgraphs
Authors: Berman Kenneth A.
Published: May 2007

An ingraph N is a subgraph of a digraph G whose edge set consists of all the edges of G that are directed into a subset X of the vertices. Set X is the generating set of N. It is proved that G contains a unique even ingraph and this ingraph is generated by the set A of vertices that root an odd number of spanning out arborescences provided A is nonempty. If A is empty, then there exist at least two even ingraphs.
Graph‐theoretic characterization of the matrix property of full irreducibility without using a transversal
Authors: Kevorkian Aram K.
Published: May 2007

In this paper we introduce the notion of strongly connected polygons in the line graph of a bipartite graph. We use this notion to give a necessary and sufficient condition for a matrix Y to be fully irreducible without the need to construct a transversal of Y. In addition, we show that the notion of strongly connected polygons forms the basis of a general theory that may be used for finding all the cycles in the directed graph of a fully irreducible matrix and for constructing all the nonzero transversals of a fully irreducible matrix.
On the use of alternating chains and hypergraphs in edge coloring
Authors: de Werra D.
Published: May 2007

Existence of some generalized edge colorings is proved by using the properties of hypergraphs as well as alternating chain methods. A general framework is given for edge colorings and some general properties of balancing are derived.
Randomly matchable graphs
Authors: Summer David P.
Published: May 2007

A graph is defined to be randomly matchable if every matching of G can be extended to a perfect matching. It is shown that the connected randomly matchable graphs are precisely K2n and Kn,n (n ≥ 1).
Orderly algorithms for generating restricted classes of graphs
Authors: Colbourn Charles J. , Read Ronald C.
Published: May 2007

Orderly algorithms for the generation of exhaustive lists of nonisomorphic graphs are discussed. The existence of orderly methods to generate the graphs with a given subgraph and without a given subgraph is established. This method can be used to list all the nonisomorphic subgraphs of a given graph, as well as to produce catalogs of Hamiltonian graphs, pancyclic graphs, degree‐constrained graphs, and other classes. A generalization of this method is given that can be used to generate lists of graphs with given girth, planar graphs, k‐colorable graphs, and k‐connected graphs, for example. Finally, these observations are employed to generate restricted classes of digraphs, notably acyclic digraphs and poset digraphs. The generation of poset digraphs is shown to supply a practical orderly method for producing a catalog of lattices. Similar observations concerning vertex addition generation methods allow one to improve on existing methods for the generation of catalog of interval and circle graphs.
On double and multiple interval graphs
Authors: Trotter William T. , Harary Frank
Published: May 2007

In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph G to be the smallest positive integer t for which there exists a function f which assigns to each vertex u of G a subset f(u) of the real line so that f(u) is the union of t closed intervals of the real line, and distinct vertices u and v in G are adjacent if and only if f(u) and f(v)meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graph Km, n has interval number ⌈(mn + 1)/(m + n)⌉.
On minimal strong blocks
Authors: Grötschel Martin
Published: May 2007

It is shown that storng blocks, i.e., digraphs that are strongly connected and have no cutnodes have an ear‐decomposition. This result is used to prove that the number q of arcs of minimal strong blocks is bounded by p ≤ q ≤ 2p – 3 and that minimal strong blocks contain at least two nodes with indegree and outdegree equal to one.
The graphs for which all strong orientations are hamiltonian
Authors: Grötschel Martin , Harary Frank
Published: May 2007

We show that the only nontrivial strongly orientable graphs for which every strong oreintation is Hamiltonian are complete graphs and cycles.
Properties of almost all graphs and complexes
Authors: Blass Andreas , Harary Frank
Published: May 2007

There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries. To this end, we propose the first‐order theory of almost all graphs by presenting Axiom n which states that for each sequence of 2n distinct vertices in a graph (u1, …, un, v1, …, vn), there exists another vertex w adjacent to each u1 and not adjacent to any vi. A simple counting argument proves that for each n, almost all graphs satisfy Axiom n. It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graph H, almost all graphs have an induced subgraph isomorphic to H. (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all grpahs are connected wiht diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicial complexes.
Graph‐theoretic parameters concerning domination, independence, and irredundance
Authors: Bollobás B. , Cockayne E. J.
Published: May 2007

A vertex x in a subset X of vertices of an undericted graph is redundant if its closed neighbourhood is contained in the union of closed neighborhoods of vertices of X – {x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X – {x}. The irredundance number ir (G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. The domination number γ(G) is the minimum cardinality taken over all dominating sets of G, and the independent domination number i(G) is the minimum cardinality taken over all maximal independent sets of vertices of G. The paper contians results that relate these parameters. For example, we prove that for any graph G, ir (G) > γ(G)/2 and for any grpah Gwith p vertices and no isolated vertices, i(G) ≤ p‐γ(G) + 1 ‐ ⌈(p ‐ γ(G))/γ(G)⌉.
A sufficient condition for equality of edge‐connectivity and minimum degree of a graph
Authors: Goldsmith Donald L. , Entringer Roger C.
Published: May 2007

Let G be a connected graph of order p ≥ 2, with edge‐connectivity κ1(G) and minimum degree δ(G). It is shown her ethat in order to obtain the equality κ1(G) = δ(G), it is sufficient that, for each vertex x of minimum degree in G, the vertices in the neighbourhood N(x) of x have sufficiently large degree sum. This result implies a previous result of Chartrand, which required that δ(G) ≥ [p/2].
Class of graphs with restricted neighborhoods
Authors: Rawlinson Kim T. , Entringer R. C.
Published: May 2007

A description is obtained for connected graphs in which a point u is adjacent of v only if u is adjacent to all points whose degree is greater than that of v. The minimum number of lines in such a grpah with all points having degree at least d is also determined. Finally, an application to communication systems is discussed.
Infinite families of biembedding numbers
Authors: Anderson I.
Published: May 2007

Let N(γ, γ′) denote the size of the smallest complete graph that cannot be edge‐partitioned into two parts embeddable in closed orientable sufaces of genera γ, γ′, respectively. Well‐known embedding theorems are used to obtain several infinite families of values of N(γ, γ′). Some related small values of N(γ, γ′) are also discussed.
Edge‐reconstruction of planar graphs with minimum valency 5
Authors: Lauri Josef
Published: May 2007

The object of this paper is to show tht every planar graph of minimum valency 5 is reconstructible from its family of edge‐deleted subgraphs.
A class of self‐complementary graphs and lower bounds of some ramsey numbers
Authors: Clapham C. R. J.
Published: May 2007

A method is described of constructing a class of self‐complementary graphs, that includes a self‐complementary graph, containing no K5, with 41 vertices and a self‐complementary graph, containing no K7, with 113 vertices. The latter construction gives the improved Ramsey number lower bound r(7, 7) ≥ 114.
Some problems in topological graph theory
Authors: Gross Jonathan L. , Harary Frank
Published: May 2007

A list of 31 problems presented here reflects some of the main trends in topological graph theory.
Note on Choudum's “chromatic bounds for a class of graphs”
Authors: Javdekar Medha
Published: May 2007

If a graph G has no induced subgraph isomorphic to K1,3′ K5‐e, or a third graph that can be selected from two specific graphs, then the chromatic number of G is either d or d + 1, where d is the maximum order of a clique in G.
Covers and strong covers in directed bipartite graphs
Authors: Vidyasankar K.
Published: May 2007

Let G be a finite graph with directed bipartition (V+, V−). Necessary and sufficient conditions are given for the existence of covers and strong covers that: (i) satisfy matching with respect to V+, and (ii) include a given set of edges that satisfies matching with respect to V+.
Three small cubic graphs with interesting hamiltonian properties
Authors: Zamfirescu Tudor
Published: May 2007

We present here three graphs, which are the smallest known ones of their kind: a cubic three‐connected planar nontraceable graph, a cubic three‐connected planar graph which is not homogeneously traceable, and a cubic one‐Hamiltonian graph which is not Hamiltonian connected.
All triangle‐graph ramsey numbers for connected graphs of order six
Authors: Faudree R. J. , Rousseau C. C. , Schelp R. H.
Published: May 2007

The Ramsey numbers r(K3′ G) are determined for all connected graphs G of order six.
The orders of graphs with prescribed degree sets
Authors: Sipka Timothy A.
Published: May 2007

The degree set 𝒟G of a graph G is the set of degrees of the vertices of G. For a finite nonempty set S of positive integers, all positive integers p are determined for which there exists a graph G of order p such that 𝒟G = S.
On the critical graph conjecture
Authors: Yap Hian Poh
Published: May 2007

Gol'dberg has recently constructed an infinite family of 3‐critical graphs of even order. We now prove that if there exists a p(≥4)‐critical graph K of odd order such that K has a vertex u of valency 2 and another vertex v ≠ u of valency ≤(p + 2)/2, then there exists a p‐critical graph of even order.
An upper bound on the length of a Hamiltonian walk of a maximal planar graph
Authors: Asano Takao , Nishizeki Takao , Watanabe Takahiro
Published: May 2007

A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p ‐ 3)/2.
Girth in digraphs
Authors: Bermond J. C. , Germa A. , Heydemann M. C. , Sotteau D.
Published: May 2007

For an integer k > 2, the best function m(n, k) is determined such that every strong digraph of order n with at least m(n, k) arcs contains a circuit of length k or less.
On the Ramsey multiplicities of graphs—problems and recent results
Authors: Burr Stefan A. , Rosta Vera
Published: May 2007

Ramsey's theorem guarantees that if G is a graph, then any 2‐coloring of the edges of a large enough complete graph yields a monochromatic copy of G. Interesting problems arise when one asks how many such G must occur. A survey of this and related problems is given, along with a number of new results.
Cycles in digraphs– a survey
Authors: Bermond J. C. , Thomassen C.
Published: May 2007

The main subjects of this survey paper are Hamiltonian cycles, cycles of prescribed lengths, cycles in tournaments, and partitions, packings, and coverings by cycles. Several unsolved problems and a bibliography are included.
The chromatic index of graphs with a spanning star
Authors: Plantholt Mike
Published: May 2007

Vizing's Theorem states that any graph G has chromatic index either the maximum degree Δ(G) or Δ(G) + 1. If G has 2s + 1 points and Δ(G) = 2s, a well‐known necessary condition for the chromatic index to equal 2s is that G have at most 2s2 lines. Hilton conjectured that this condition is also sufficient. We present a proof of that conjecture and a corollary that helps determine the chromatic index of some graphs with 2s points and maximum degree 2s − 2.
A duality theorem for graph embeddings
Authors: Jackson Brad , Parsons T. D. , Pisanski Tomaž
Published: May 2007

A generalized type of graph covering, called a “Wrapped quasicovering” (wqc) is defined. If K, L are graphs dually embedded in an orientable surface S, then we may lift these embeddings to embeddings of dual graphs K̃,L̃ in orientable surfaces S̃, such that S̃ are branched covers of S and the restrictions of the branched coverings to K̃,L̃ are wqc's of K, L. the theory is applied to obtain genus embeddings of composition graphs G[nK1] from embeddings of “quotient” graphs G.
The smallest graph of girth 6 and valency 7
Authors: O'Keefe M. , Wong P. K.
Published: May 2007

With the aid of a computer. we give a regular graph of girth 6 and valency 7, which has 90 vertices and show that this is the unique smallest graph with these properties.
On a graph of O'Keefe and wong
Authors: Ito T.
Published: May 2007

The graph of O'Keefe and Wong, with valency 7, girth 6, and 90 vertices, is constructed as a 3‐fold covering graph, and it is shown that there is a unique covering graph with these properties.
A graph and its complement with specified properties. IV. Counting self‐complementary blocks
Authors: Akiyama Jin , Harary Frank
Published: May 2007

In this series, we investigate the conditions under which both a graph G and its complement G possess certain specified properties. We now characterize all the graphs G such that both G and G have the same number of endpoints, and find that this number can only be 0 or 1 or 2. As a consequence, we are able to enumerate the self‐complementary blocks.
A note on constructive methods for ramsey numbers
Authors: Chung F. R. K.
Published: May 2007

Let r(k) denote the least integer n‐such that for any graph G on n vertices either G or its complement G contains a complete graph Kk on k vertices. in this paper, we prove the following lower bound for the Ramsey number r(k) by explicit construction: r(k) ≥ exp (c(Log k)4/3[(log log k)1/3] for some constant c> 0.
On the reconstruction of locally finite trees
Authors: Andreae Thomas
Published: May 2007

We prove a theorem saying, when taken together with previous results of Bondy, Hemminger, and Thomassen, that every locally finite, infinite tree not containing a subdivision of the dyadic tree (i. e., the regular tree of degree 3) is uniquely determined, up to isomorphism, from its collection of vertex‐deleted subgraphs. Furthermore, as another partial result concerning the reconstruction of locally finite trees, we show that the same is true for locally finite trees whose set of vertices of degree s is nonempty and finite (for some positive integer s).
Long paths and cycles in oriented graphs
Authors: Jackson Bill
Published: May 2007

We obtain several sufficient conditions on the degrees of an oriented graph for the existence of long paths and cycles. As corollaries of our results we deduce that a regular tournament contains an edge‐disjoint Hamilton cycle and path, and that a regular bipartite tournament is hamiltonian.
A construction of chromatic index critical graphs
Authors: Yap Hian Poh
Published: May 2007

We prove that if K is an undirected, simple, connected graph of even order which is of class one, regular of degree p ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph G obtained from K by splitting any vertex is p‐critical. We find that various constructions of critical graphs by S. Fiorini are special cases of a corollary of this result.
An upper bound on the size of the largest cliques in a graph
Authors: Billionnet Alain
Published: May 2007

We produce in this paper an upper bound for the number of vertices existing in a clique of maximum cardinal. The proof is based in particular on the existence of a maximum cardinal clique that contains no vertex x such that the neighborhood of x is contained in the neighborhood of another vertex y.
Hamiltonian groups are color‐graph‐hamiltonian
Authors: Klerlein Joseph B. , Starling A. Gregory
Published: May 2007

A group Γ is said to be color ‐graph ‐hamiltonian if Γ has a minimal generating set Δ such that the Cayley color graph DΔ(Γ) is hamiltonian. It is shown that every hamiltonian group is color ‐graph ‐hamiltonian.
A note on path and cycle decompositions of graphs
Authors: Decaen Dom
Published: May 2007

In the study of decompositions of graphs into paths and cycles, the following questions have arisen: Is it true that every graph G has a smallest path (resp. path‐cycle) decomposition P such that every odd vertex of G is the endpoint of exactly one path of P? This note gives a negative answer to both questions.
On strongly regular self ‐ complementary graphs
Authors: Ruiz Sergio
Published: May 2007

It is shown that certain conditions assumed on a regular self‐complementary graph are not sufficient for the graph to be strongly regular, answering in the negative a question posed by Kotzig in [1].
Kuratowski's theorem
Authors: Thomassen Carsten
Published: May 2007

We present three short proofs of Kuratowski's theorem on planarity of graphs and discuss applications, extensions, and some related problems.
An extremal problem for paths in bipartite graphs
Authors: Gyárfás A. , Rousseau C. C. , Schelp R. H.
Published: May 2007

A formula is found for the maximum number of edges in a graph G ⊆ K(a, b) which contains no path P2l for l > c. A similar formula is found for the maximum number of edges in G ⊆ K(a, b) containing no P2l + 1 for l > c. In addition, all extremal graphs are determined.
A second trivalent graph with 58 vertices and girth 9
Authors: Evans C. W.
Published: May 2007

The trivalent graph of girth 9 with 58 vertices discovered by N. L. Biggs and M. J. Hoare is not the only graph of this kind.
A short proof for the Faudree‐Schelp theorem on path‐connected graphs
Authors: Xiao‐Tao Cai
Published: May 2007

In this note a shortened proof is given for the Faudree—Schelp theorem on path‐connected graphs.
Graphs with given group and given constant link
Authors: Vogler Walter
Published: May 2007

A graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link .L Sabidussi proved that for any finite group F and any n ⩾ 3 there are infinitely many n‐regular connected graphs G with AutG ≅ Γ. We will prove a stronger result: For any finite group Γ and any link graph L with at least one isolated vertex and at least three vertices there are infinitely many connected graphs G with constant link L and AutG ≅ Γ.
Edge‐coloring of multigraphs: Recoloring technique
Authors: Goldberg Mark K.
Published: May 2007

New upper and lower bounds for the chromatic index of a finite muitigraph are obtained. A complete description is given of multigraphs satisfying χ′ > 1/8(9ρ + 6) where χ′ and ρ denote the chromatic index and the maximum vertex degree of a multigraph. Some new and old conjectures are discussed.
Hamiltonian results in K1,3‐free graphs
Authors: Matthews M. M. , Sumner D. P.
Published: May 2007

There have been a number of results dealing with Hamiltonian properties in powers of graphs. In this paper we show that the square and the total graph of a K1,3‐free graph are vertex pancyclic. We then discuss some of the relationships between connectivity and Hamiltonian properties in K1,3‐free graphs.
Forbidden subgraphs and hamiitonian properties in the square of a connected graph
Authors: Gould Ronald J. , Jacobson Michael S.
Published: May 2007

Various Harniltonian‐like properties are investigated in the squares of connected graphs free of some set of forbidden subgraphs. The star K1,4 the subdivision graph of K1,3, and the subdivision graph of K1,3 minus an endvertex play central roles. In particular, we show that connected graphs free of the subdivision graph of K1,3 minus an endvertex have vertex pancyclic squares.
Minimum K‐hamiltonian graphs
Authors: Wong W. W. , Wong C. K.
Published: May 2007

We consider two new classes of graphs arising from reliability considerations in network design. We want to construct graphs with a minimum number of edges which remain Hamiltonian after k edges (or k vertices) have been removed. A simple construction is presented for the case when k is even. We show that it is minimum k‐edge Hamiltonian. On the other hand, Chartrand and Kapoor previously proved that this class of graphs was also minimum k‐vertex Hamiltonian. The case when k is large (odd or even) is also considered. Some results about directed graphs are also presented.
On the number of vertices of given degree in a random graph
Authors: Palka Zbigniew
Published: May 2007

This note can be treated as a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G ∈ 𝒢(n, p) asymptotically has a normal distribution.
The ramsey numbers for stripes and one complete graph
Authors: Lorimer Peter
Published: May 2007

The Ramsey numbers r(Kp, n1P2,…,ndP2), p > 2, are calculated.
Long paths and large cycles in finite graphs
Authors: Enomoto Hikoe
Published: May 2007

Ore‐type sufficient conditions ensuring the existence of a large cycle passing through any given path of length s for (s + 2)‐connected graphs are given, and the extremal cases are characterized.
On hamiltonian line graphs
Authors: Clark Lane
Published: May 2007

We give best possible Ore‐like conditions for a graph so that its line graph is Hamiltonian.
The linear arboricity of some regular graphs
Authors: Enomoto Hikoe , Péroche Bernard
Published: May 2007

We prove that the linear arboricity of every 5‐regular graph is 3. That is, the edges of any 5‐regular graph are covered by three linear forests. We also determine the linear arboricity of 6‐regular graphs and 8‐regular graphs. These results improve the known upper bounds for the linear arboricity of graphs with given maximum degree.
On a problem of a. kotzig concerning factorizations of 4‐regular graphs
Authors: Zelinka Bohdan
Published: May 2007

The paper gives a solution of a problem of A. Kotzǐg. This problem concerns the 4‐regular graphs G with the property that in every decomposition of G into two edge‐disjoint 2‐regular factors at least one factor is a Hamiltonian circuit in G.
Box‐threshold graphs
Authors: Peled Uri N. , Simeone Bruno
Published: May 2007

A graph is called box‐threshold when all pairs of vertices with incomparable neighborhoods have the same degree. Several properties of box‐threshold graphs, generalizing properties of threshold graphs, are proved. A transportation model with priority constraints is used to characterize their degree sequences. Further characterizations are given using the concept of the frame of a graph.
Connected, locally 2‐connected, K1,3‐free graphs are panconnected
Authors: Kanetkar S. V. , Rao P. R.
Published: May 2007

A graph G is locally n‐connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n‐connected. We prove that every connected, locally 2‐connected graph containing no induced subgraph isomorphic to K1,3 is panconnected.
Chromatic uniqueness and equivalence of K4 homeomorphs
Authors: Whitehead Earl Glen , Zhao Lian‐Chang
Published: May 2007

We derive a new formula for the chromatic polynomial of any K4 homeomorph. We obtain a large family of chromatically unique K4 homeomorphs. We obtain seven infinite pairs of chromatically equivalent nonisomorphic K4 homeomorphs.
The cycle space of an embedded graph
Authors: Richter B. , Shank H.
Published: May 2007

Let G be a connected graph with edge set E embedded in the surface ∑. Let G° denote the geometric dual of G. For a subset d of E, let τd denote the edges of G° that are dual to those edges of G in d. We prove the following generalizations of well‐known facts about graphs embedded in the plane.

(1) b is a boundary cycle in G if and only if τb is a cocycle in G°.

(2) If T is a spanning tree of G, then τ(E/T) contains a spanning tree of G°.

(3) Let T be any spanning tree of G and, for e ϵ E/T, let T(e) denote the fundamental cycle of e. Let U ∪ E/T. Then τU is a spanning tree of G° if and only if the set of face boundaries, less any one, together with the set {T(e); e ϵ E/(T ∪ U)} is a basis for the cycle space of G.
Cutpoints and the chromatic polynomial
Authors: Whitehead Earl Glen , Zhao Lian‐Chang
Published: May 2007

We prove that the multiplicity of the root 1 in the chromatic polynomial of a simple graph G is equal to the number of nontrivial blocks in G. In particular, a connected simple graph G has a cutpoint if and only if its chromatic polynomial is divisible by (λ – 1)2. We apply this theorem to obtain some chromatic equivalence and uniqueness results.
Doubly eulerian trails on rectangular grids
Authors: Brenner J. L. , Lyndon R. C.
Published: May 2007

Let K be the 1‐skeleton of the regular tessellation of Euclidean n‐space by n‐cubes, n ≥ 2. We show that K admits a doubly Eulerian trail (simply Eulerian trail), that is, a doubly infinite path π = … e−1e0e1 … where, out of each pair {e, e−1} of oppositely directed edges, both (exactly one) appear(s) exactly once in π, and where no ei+1 = ei−1 (there are no U‐turns).
Face colorings of embedded graphs
Authors: Archdeacon Dan
Published: May 2007

We characterize those graphs which have at least one embedding into some surface such that the faces can be properly colored in four or fewer colors. Embeddings into both orientable and nonorientable surfaces are considered.
The multiplicity of 1‐factors in the square of a graph
Authors: Hendry G. R. T.
Published: May 2007

Several authors have shown that if G is a connected graph of even order then its square G2 has a 1‐factor. We show that the square of any connected graph of order 2n has at least n 1‐factors and describe all the extremal graphs.
On the reconstruction of rayless infinite forests
Authors: Andreae Thomas , Schmidt Rüdiger
Published: May 2007

A graph G is called strongly p‐reconstructible if it is (up to isomorphism) uniquely determined by the collection of its pairwise nonisomorphic subgraphs G – v where v is a pendent vertex of G. Using previous results of the second author concerning the structure of infinite rayless graphs it is shown that every rayless forest with an infinite edge‐set is strongly p‐reconstructible. This result is applied to the classical reconstruction problem to find that every infinite rayless forest G with a finite number of components is reconstructible; i.e., G is (up to isomorphism) uniquely determined by its collection of vertex‐deleted subgraphs. Furthermore, an example is given which shows that nonreconstructible rayless forests with a countable number of components exist.
Note on the existence of directed (k + 1)‐cycles in diconnected complete k‐partite digraphs
Authors: Balakrishnan R. , Paulraja P.
Published: May 2007

A graph is constructed to provide a negative answer to the following question of Bondy: Does every diconnected orientation of a complete k‐partite (k ≥ 5) graph with each part of size at least 2 yield a directed (k + 1)‐cycle?
A simple proof of Menger's theorem
Authors: McCuaig William
Published: May 2007

A proof of Menger's theorem is presented.
A digraph represented by a family of boxes or spheres
Authors: Maehara Hiroshi
Published: May 2007

As a digraph analog of the intersection graph, a family of pointed sets represents a digraph. This paper studies those digraphs represented by families of pointed convex sets, pointed boxes, and pointed spheres, in Euclidean spaces.
On the distribution of cycle lengths in graphs
Authors: Gyárfás A. , Komlós J. , Szemerédi E.
Published: May 2007

The set of different cycle lengths of a graph G is denoted by C(G). We study how the distribution of C(G) depends on the minimum degree of G. We prove two results indicating that C(G) is dense in some sense. These results lead to the solution of a conjecture of Erdös and Hajnal stating that for suitable positive constants a, b the following holds: magnified image where δ(G) denotes the minimum degree of G.
The chromatic index of graphs of even order with many edges
Authors: Chetwynd A. G. , Hilton A. J. W.
Published: May 2007

We show that, for r = 1, 2, a graph G with 2n + 2 (≥6) vertices and maximum degree 2n + 1 ‐ r is of Class 2 if and only if |E(G/v)| > () ‐ rn, where v is a vertex of G of minimum degree, and we make a conjecture for 1 ≤ r ≤ n, of which this result is a special case. For r = 1 this result is due to Plantholt.
The decomposition of trees into subtrees
Authors: Caro Yair
Published: May 2007

A necessary condition for the decomposition of a tree T into subtrees, each isomorphic to a tree from a given set of trees is presented. We also present a characterization of the set of trees for which the condition is sufficient. Many examples are given.
Circulants and their connectivities
Authors: Boesch F. , Tindell R.
Published: May 2007

There is diverse literature on various properties of a class of graphs known as circulants. We present a new result which answers the previously unsolved question of characterizing the connection sequence of circulants having point connectivity equal to point degree. We also develop some theorems regarding a new generalization of connectivity known as super‐connectivity. In addition, we give a survey of published results pertinent to the study of connectivity of circulants.
Retracts of hypercubes
Authors: Bandelt H. J.
Published: May 2007

An induced subgraph G of a graph H is a retract of H if there is an edge‐preserving map f from H onto G such that f|G is the identity map on G. A median graph is a connected graph such that for any three vertices u,v and w, there exists a unique vertex x which lies simultaneously on some shortest (u,v)‐, (v,w)‐, and (w,u)‐paths. It is shown that a graph G is a retract of some hypercube if and only if G is a median graph.
Diameter bounds for altered graphs
Authors: Chung F. R. K. , Garey M. R.
Published: May 2007

The main question addressed in this article is the following: If t edges are removed from a (t + 1) edge‐connected graph G having diameter D, how large can the diameter of the resulting graph be? (The diameter of a graph is the maximum, over all pairs of vertices, of the length of the shortest path joining those vertices.) We provide bounds on this value that imply that the maximum possible diameter of the resulting graph, for large D and fixed t, is essentially (t + 1) · D. The bulk of the proof consists of showing that, if t edges are added to an n‐vertex path Pn, then the diameter of the resulting graph is at least (n/(t + 1)) ‐ 1. Using a similar proof, we also show that if t edges are added to an n‐vertex cycle Cn, then the least possible diameter of the resulting graph is (for large n) essentially n/(t + 2) when t is even and n/(t + 1) when t is odd. Examples are given in all these cases to show that there exist graphs for which the bounds are achieved. We also give results for the corresponding vertex deletion problem for general graphs. Such results are of interest, for example, when studying the potential effects of node or link failures on the performance of a communication network, especially for networks in which the maximum time‐delay or signal degradation is directly related to the diameter of the network.
An upper bound for the k‐domination number of a graph
Authors: Cockayne E. J. , Gamble B. , Shepherd B.
Published: May 2007

The k‐domination number of a graph G, γk(G), is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k, then γk(G) ≤ kp/(k + 1).
The square of a connected S(K1,3)‐free graph is vertex pancyclic
Authors: Hendry George , Vogler Walter
Published: May 2007

We prove the conjecture of Gould and Jacobson that a connected S(K1,3)‐free graph has a vertex pancyclic square. Since S(K1,3)2 is not vertex pan‐cyclic, this result is best possible.
Cataloguing the graphs on 10 vertices
Authors: Cameron R. D. , Colbourn C. J. , Read R. C. , Wormald N. C.
Published: May 2007

We describe the production of a catalogue of all the nonisomorphic graphs on 10 vertices by means of a computer program. The basic program generated all the nonisomorphic graphs with a given degree sequence. Some tables, derived from the catalogue, concerning the numbers of automorphisms of these graphs are given at the end of the paper.
Enumeration of cyclically 4‐connected cubic graphs
Authors: Wormald Nicholas C.
Published: May 2007

The number of labeled cyclically 4‐connected cubic graphs on n vertices is shown to satisfy a simple recurrence relation. The proof involves the unique decomposition of 3‐connected cubic graphs into cyclically 4‐connected components.