bluuebunny/crossref_metadata_2025_split huggingface dataset:
Mechanism of naked DNA clearance after intravenous injection
Authors: Liu Feng , Shollenberger Lisa M. , Conwell Christine C. , Yuan Xing , Huang Leaf 
Published: May 2007

AbstractBackgroundInjection of naked DNA has been viewed as a safer alternative to current gene delivery systems; however, the rate of clearance from the circulation has been a constant barrier in developing these methods. Naked DNA after intravenous (i.v.) injection will be taken up by the liver and depredated by serum nucleases.Materials and methodsOur study examines the mechanisms involved in clearance of naked DNA by each compartment, the blood and the liver, in anin vivomouse model. Confocal microscopy and transmission electron microscopy were employed to identify the type of cells taking up DNA and the barrier to DNA access to hepatocytes, respectively.ResultsOur data showed the liver could take up over 50% of 5 µg perfused pDNA, with a maximum 25 µg of pDNA during a single pass, and a slower clearance rate compared to that of liver uptake. It was demonstrated that naked DNA is primarily taken up by the liver endothelial cells and this endothelial barrier to transfection could be overcome by manually massaging the liver, which enlarges the fenestrae.ConclusionsThis study clarifies the mechanism by which naked DNA is eliminated from the circulation after i.v. injection, focusing on the role of both the liver and blood compartmentsin vivo(i.e. mouse). With this knowledge, we can more clearly understand the mechanism of naked DNA clearance and develop more efficient strategies for DNA transferin vivo. Copyright © 2007 John Wiley & Sons, Ltd.
A canonical representation of trivalent hamiltonian graphs
Authors: Frucht Roberto 
Published: May 2007

AbstractA canonical representation of trivalent hamiltonian graphs in the form of “span lists” had been proposed by J. Lederberg. It is here presented in a modified form due to H. S. M. Coxeter and the author, and therefore called “LCF notation.” This notation has the advantage of being more concise than Lederberg's original span lists whenever the graph has a hamiltonian circuit with rotational symmetry. It is also useful as a method for a systematic classification of trivalent hamiltonian graphs and allows one to define for such graphs two interesting properties, called, respectively, “antipalindromic” and “quasiantipalindromic.”.
On induced subgraphs of a block
Authors: Nebeský Ladislav 
Published: May 2007

AbstractIf G is a block, then a vertex u of G is called critical if G ‐ u is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each edge is incident with at least one critical vertex and b) each vertex of degree two is critical. Let G be a semicritical block with at least six vertices. It is proved that A) there exist distinct vertices u2, v1, u2, and v2 of degree two in G such that u1v1 and u2v2 are edges of G, and u1v2, and u2v2 are edges of the complement of G, and B) the complement of G is a block with no critical vertex of degree two.
The biparticity of a graph
Authors: Harary Frank , Hsu Derbiau , Miller Zevi 
Published: May 2007

AbstractThe biparticity β(G) of a graph G is the minimum number of bipartite graphs required to cover G. It is proved that for any graph G, β(G) = {log2χ(G)}. In view of the recent announcement of the Four Color Theorem, it follows that the biparticity of every planar graph is 2.
Graph reconstruction—a survey
Authors: Bondy J. A. , Hemminger R. L. 
Published: May 2007

AbstractThe Reconstruction Conjecture asserts that every finite simple undirected graph on three or more vertices is determined, up to isomorphism, by its collection of vertex‐deleted subgraphs. This article reviews the progress made on the conjecture since it was first formulated in 1941 and discusses a number of related questions.
The graph isomorphism disease
Authors: Read Ronald C. , Corneil Derek G. 
Published: May 2007

AbstractThe graph isomorphism problem—to devise a good algorithm for determining if two graphs are isomorphic—is of considerable practical importance, and is also of theoretical interest due to its relationship to the concept of NP‐completeness. No efficient (i.e., polynomial‐bound) algorithm for graph isomorphism is known, and it has been conjectured that no such algorithm can exist. Many papers on the subject have appeared, but progress has been slight; in fact, the intractable nature of the problem and the way that many graph theorists have been led to devote much time to it, recall those aspects of the four‐color conjecture which prompted Harary to rechristen it the “four‐color disease.” This paper surveys the present state of the art of isomorphism testing, discusses its relationship to NP‐completeness, and indicates some of the difficulties inherent in this particularly elusive and challenging problem. A comprehensive bibliography of papers relating to the graph isomorphism problem is given.
Line pseudodigraphs
Authors: Hemminger Robert L. , Klerlein Joseph B. 
Published: May 2007

AbstractA new definition of the line digraph is given that reflects all types of arc adjacencies in the original digraph. The definition also allows for loops and multiple arcs, hence it is called the line pseudodigraph. A Whitney type theorem is then given; that is, the relationship between pseudodigraphs having the same line pseudodigraph is determined.
Hamiltonian cycles in cayley color graphs
Authors: Klerlein Joseph B. 
Published: May 2007

AbstractA group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph DΔ(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are also investigated.
On stable crossing numbers
Authors: Kainen Paul C. , White Arthur T. 
Published: May 2007

AbstractResults giving the exact crossing number of an infinite family of graphs on some surface are very scarce. In this paper we show the following: for G = Qn × K4.4, cry(G)‐m(G) = 4m, for 0 ⩽ = m ⩽ 2n. A generalization is obtained, for certain repeated cartesian products of bipartite graphs. Nonorientable analogs are also developed.
An upper bound on the size of a largest clique in a graph
Authors: Geoffroy Dennis P. , Sumner David P. 
Published: May 2007

AbstractA graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point‐determining graph is the set GO of all vertices, v, such that G–v is point determining. In this paper we show that the size, ω(G), of a maximum clique in G satisfies ω(G) ⩽ 2|π (G)O|, where π(G) (the point determinant of G) is obtained from G by identifying vertices which have the same neighborhood.
A note on graphs spanned by Eulerian graphs
Authors: Pulleyblank W. R. 
Published: May 2007

AbstractWe show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP‐complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at every node.
Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
Authors: Oberly David J. , Sumner David P. 
Published: May 2007

AbstractA graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on p ≥ 3 vertices and having no induced K1,3 is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtained as corollaries.
A characterization of ptolemaic graphs
Authors: Howorka Edward 
Published: May 2007

AbstractA connected graph G is ptolemaic provided that for each four vertices Ui, 1 ≤ i ≤ 4, of G, the six distances dii = dG (Ui, Ui), i ≠ j satisfy the inequality d12d34 ≤ d13d24 + d14d23 (shown by Ptolemy to hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showed that weakly geodetic ptolemaic graphs are precisely Husimi trees (in particular, trees are ptolemaic). in the present paper several characterizations of ptolemaic graphs are given. It is shown, for example, that a connected graph G is ptolemaic if and only iffor each nondisjoint cliques P, Q of G, their intersection is a cutset of G which separates P‐Q and Q‐P. An operation is exhibited which generates all finite ptolemaic graphs from complete graphs.
Maximal non‐ hamilton‐laceable graphs
Authors: Simmons Gustavus J. 
Published: May 2007

AbstractFor bipartite graphs the property of being Hamilton laceable is analogous to the property of being Hamilton connected for simple graphs. in this paper it is proven that all of the graphs obtained by deleting fewer than m − 1 edges from either of the complete bipartite graphs Km, m or Km, m+1 are Hamilton laceable. It is also proven that the deletion of m − 1 edges results in a non‐Hamiltonlaceable graph if and only if the graph is either the complement of the star K1,m−1 in Km, m or Km, m+1 or else the complement in K3,3 of a pair of nonadjacent edges.
Generating all 4‐regular planar graphs from the graph of the octahedron
Authors: Lehel Jenö 
Published: May 2007

AbstractIt has been communicated by P. Manca in this journal that all 4‐regular connected planar graphs can be generated from the graph of the octahedron using simple planar graph operations. We point out an error in the generating procedure and correct it by including an additional operation.
Harmonious labelings of windmill graphs and related graphs
Authors: Hsu D. Frank 
Published: May 2007

AbstractA strongly harmonious labeling is the nonmodular version of a harmonious labeling. The windmill graph K(t)n is the graph consisting of t copies of the complete graph Kn with a vertex in common. It is shown that, for t ≥ 1, K(t)n is strongly harmonious and so harmonious by drawing on partitions already available from the construction of cyclic neofields. Other irregular windmill graphs can be shown to be strongly harmonious in a similar way.
On maximum bipartite subgraphs
Authors: Malle Günther 
Published: May 2007

AbstractIn this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipartite subgraphs of cubic graphs are investigated. It is shown that cubic graphs can be built up from five building stones (called elementary paths). Finally the investigation of a special class of cubic graphs yields a theorem which characterizes the Petersen graph and the dodecahedron graph by means of their maximum bipartite subgraphs.
Vertices of given degree in a random graph
Authors: Bollobás Béla 
Published: May 2007

AbstractThis paper concerns the degree sequence d1 ≥ d2 ≥ … ≥ dn of a randomly labeled graph of order n in which the probability of an edge is p(n) ≦ 1/2. Among other results the following questions are answered. What are the values of p(n) for which d1, the maximum degree, is the same for almost every graph? For what values of p(n) is it true that d2 > d2 for almost every graph, that is, there is a unique vertex of maximum degree? The answers are (essentially) p(n) = o(logn/n/n) and p(n)n/logn → ∞. Also included is a detailed study of the distribution of degrees when 0 < lim n p(n)/log n ≦ lim n p(n)/log n < ∞.
A shortness exponent for r‐regular r‐connected graphs
Authors: Jackson Brad , Parsons T. D. 
Published: May 2007

AbstractLet r≧ 3 be an integer. It is shown that there exists ε= ε(r), 0 < ε < 1, and an integer N = N(r) > 0 such that for all n ≧ N (if r is even) or for all even n ≧ N(if r is odd), there is an r‐connected regular graph of valency r on exactly n vertices whose longest cycles have fewer than nε vertices.
Atoll decompositions of graphs
Authors: Buckley Fred 
Published: May 2007

AbstractAn island decomposition of a graph G consists of a set of vertex‐disjoint paths which cover the vertex set of G. If the endpoints of the paths are mutually nonadjacent, then we have an atoll decomposition. We characterize graphs requiring two paths in an island decomposition yet having no atoll decomposition. Results are given relating atoll decompositions to cutpoints and Hamiltonian blocks.
Bounds for the ramsey number of a disconnected graph versus any graph
Authors: Gould Ronald J. , Jacobson Michael S. 
Published: May 2007

AbstractBounds are determined for the Ramsey number of the union of graphs versus a fixed graph H, based on the Ramsey number of the components versus H. For certain unions of graphs, the exact Ramsey number is determined. From these formulas, some new Ramsey numbers are indicated. In particular, ifmagnified image.Where ki is the number of components of order i and t1 (H) is the minimum order of a color class over all critical colorings of the vertices of H, thenmagnified image.
Geodesic subgraphs
Authors: Batten Lynn Margaret 
Published: May 2007

AbstractDefine a geodesic subgraph of a graph to be a subgraph H with the property that any geodesic of two points of H is in H. The trivial geodesic subgraphs are the complete graphs Kn' n ≧ 0, and G itself. We characterize all (finite, simple, connected) graphs with only the trivial geodesic subgraphs, and give an algorithm for their construction. We do this also for triangle‐free graphs.
Interpolation theorem for the number of end‐vertices of spanning trees
Authors: Schuster Seymour 
Published: May 2007

AbstractThe following interpolation theorem is proved: If a graph G contains spanning trees having exactly m and n end‐vertices, with m < n, then for every integer k, m < k < n, G contains a spanning tree having exactly k end‐vertices. This settles a problem posed by Chartrand at the Fourth International Conference on Graph Theory and Applications held in Kalamazoo, 1980.
On the average shape of simply generated families of trees
Authors: Kirschenhofer Peter 
Published: May 2007

AbstractThis paper deals with the limiting distribution of the level number of the jth leaf of a planted plane tree (where leaves are enumerated from left to right) for the so‐called “simply generated families” introduced by Meir and Moon. The mathematical apparatus is determined by the idea of an asymptotic analysis of a given sequence of numbers by studying the location and nature of the singularities of appropriate generating functions.
Embeddings of bipartite graphs
Authors: Abu‐Sbeih Mohammed , Parsons T. D. 
Published: May 2007

AbstractIf G is a bipartite graph with bipartition A, B then let Gm,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a1, …, am, each vertex b of B by an independent set b1,…, bn, and each edge ab of G by the complete bipartite graph with edges aibj (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of Gm,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess‐current graphs.” They include new genus embeddings for a large class of bipartite graphs.
On Ramsey numbers involving starlike multipartite graphs
Authors: Burr S. A. , Faudree R. J. , Rousseau C. C. , Schelp R. H. 
Published: May 2007

AbstractThe Ramsey number r(G, H) is evaluated exactly in certain cases in which both G and H are complete multipartite graphs K(n,1, n2, …. nk). Specifically, each of the following cases is handled whenever n is sufficiently large: r(K(1, m1, …. mk), K(1, n)), r(K(1, m), K(n1, …. nk, n)), provided m ≧ 4, and r(K(1, 1, m), K(nk, …, nk, n)).
A generalization of chordal graphs
Authors: Seymour P. D. , Weaver R. W. 
Published: May 2007

AbstractIn a 3‐connected planar triangulation, every circuit of length ≥ 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are “separated” by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In this paper we prove his conjecture, that if G is simple and 3‐connected and every circuit of length ≥ 4 has at least two “bridges,” then G may be built up by “clique‐sums” starting from complete graphs and planar triangulations. This is a generalization of Dirac's theorem about chordal graphs.
On smallest regular graphs with a given isopart
Authors: Fink John Frederick 
Published: May 2007

AbstractFor a nonempty graph, G, we define p(G) and r(G) to be respectively the minimum order and minimum degree of regularity among all connected regular graphs H having a nontrivial decomposition into subgraphs isomorphic to G. By f(G), we denote the least integer t for which there is a connected regular graph H having a decomposition into t subgraphs isomorphic to G. In this article, the values of these parameters are determined for complete graphs, cycles, and stars. Furthermore, we show that Δ(T) ⩽ r(T) ⩽ δ (T) + 1 for every tree T. and r(T) Δ(T) if the maximum degree Δ(T) is even.
Rao's conjecture on self‐complementary graphs with K‐factors
Authors: Ando Kiyoshi 
Published: May 2007

AbstractRao posed the following conjecture, “Let G be a self‐complementary graph of order p, π = (d1 … dp) be its degree sequence. Then G has a k‐factor if and only if π − k, = (d1 − k, … dP − k) is graphical.” We construct a family of counterexamples for this conjecture for every k ⩾ 3.
[a,b]‐factorization of a graph
Authors: Kano Mikio 
Published: May 2007

AbstractLet a and b be integers such that 0 ⩽ a ⩽ b. Then a graph G is called an [a, b]‐graph if a ⩽ dG(x) ϵ b for every x ϵ V(G), and an [a, b]‐factor of a graph is defined to be its spanning subgraph F such that a ⩽ dF(x) ⩽ b for every vertex x, where dG(x) and dF(x) denote the degrees of x in G and F, respectively. If the edges of a graph can be decomposed into [a.b]‐factors then we say that the graph is [2a, 2a]‐factorable. We prove the following two theorems: (i) a graph G is [2a, 2b)‐factorable if and only if G is a [2am,2bm]‐graph for some integer m, and (ii) every [8m + 2k, 10m + 2k]‐graph is [1,2]‐factorable.
Packing a tree with a graph of the same size
Authors: Slater P. J. , Teo S. K. , Yap H. P. 
Published: May 2007

AbstractWe prove that if T is a tree of order p ⩾ 5 and G is a graph of order p and size p ‐ 1 such that neither T nor G is a star, then T can be embedded in G, the complement of G.
Threshold characterization of graphs with dilworth number two
Authors: Benzaken C. , Hammer P. L. , de Werra D. 
Published: May 2007

AbstractA graph with nodes 1, …, n is a threshold signed graph if one can find two positive real numbers S, T and real numbers a1, …, an associated with the vertices in such a way that i, j are linked iff either |ai + aj| ≥ S or |ai ‐ aj| ≥ T. Such graphs generalize threshold graphs. It is shown that these graphs are precisely the graphs with Dilworth number at most two (the Dilworth number is the maximum number of pairwise incomparable vertices in the vicinal preorder). Some other properties of this subclass of perfect graphs are also presented. The graphs considered in this paper are finite simple graphs G = (V, E), where V is the vertex set of G and E a subset of pairs of G. For x V, N(x) denotes the neighbor set of x: N(x) = {y | {x, y} E}.
The frame dimension and the complete overlap dimension of a graph
Authors: Steif Jeffrey E. 
Published: May 2007

AbstractRoberts (F. S. Roberts, On the boxicity and cubicity of a graph. In Recent Progress in Combinatorics, W. T. Tutte, ed. Academic, New York (1969)), studied the intersection graphs of closed boxes (products of closed intervals) in Euclidean n‐space, and introduced the concept of the boxicity of a graph G, the smallest n such that G is the intersection graph of boxes in n‐space. In this paper, we study the intersection graphs of the frames or boundaries of such boxes. We study the frame dimension of a graph G—the smallest n such that G is the intersection graph of frames in n‐space. We also study the complete overlap dimension of a graph, a notion that is almost equivalent. The complete overlap dimension of a graph G is the smallest dimension in which G can be represented by boxes that intersect but are not completely contained in one another. We will prove that these dimensions are in almost all cases the same and that they both can become arbitrarily large. We shall also obtain a bound for these dimensions in terms of boxicity.
A note on the matching numbers of triangle‐free graphs
Authors: Frucht Roberto W. , Giudici Reinaldo E. 
Published: May 2007

AbstractFor the sake of brevity the absolute values of the coefficients of the matching polynomial of a graph are called matching numbers in this note. It is shown that for a triangle‐free graph these numbers coincide with the coefficients of the chromatic polynomial of its complement when this polynomial is written in factorial form.As an application it is mentioned that the coefficients of every rook polynomial are at the same time coefficients of some chromatic polynomial.
Families of graphs complete for the strong perfect graph Conjecture
Authors: Corneil D. G. 
Published: May 2007

AbstractThe Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true iff it is true on these restricted families. These appear to be the first results of this type.
Asymptotic enumeration of labeled multigraphs by vertices, edges, and degree parities
Authors: Bender Edward A. , Bruce Richmond L. 
Published: May 2007

AbstractWe show that the number of labeled (n, q)‐multigraphs with some specified p vertices of odd degree is asymptotically independent of p and is in fact asymptotically 21−n times the number of (n, q)‐multigraphs. We determine the asymptotic number of (n, q)‐multigraphs.
Convex labelings of trees
Authors: Dow Stephen J. , Rall Douglas F. , Slater Peter J. 
Published: May 2007

AbstractA convex labeling of a tree T of order n is a one‐to‐one function f from the vertex set of T into the nonnegative integers, so that f(y) ⩽ (f(x) + f(z))/2 for every path x, y, z of length 2 in T. If, in addition, f(v) ⩽ n − 1 for every vertex v of T, then f is a perfect convex labeling and T is called a perfectly convex tree. Jamison introduced this concept and conjectured that every tree is perfectly convex. We show that there exists an infinite class of trees, none of which is perfectly convex, and in fact prove that for every n there exists a tree of order n which requires a convex labeling with maximum value at least 6n/5 – 22. We also prove that every tree of order n admits a convex labeling with maximum label no more than n2/8 + 2. In addition, we present some constructive methods for obtaining perfect convex labelings of large classes of trees.
A sufficient condition for a digraph to be kernel‐perfect
Authors: Duchet P. 
Published: May 2007

AbstractGaleana‐Sanchez and Neumann‐Lara proved that a sufficient condition for a digraph to have a kernel (i.e., an absorbent independent set) is the following: (P) every odd directed cycle possesses at least two directed chords whose terminal endpoints are consecutive on the cycle. Here it is proved that (P) is satisfied by those digraphs having these two properties: (i) the reversal of every 3‐circuit is present, and (ii) every odd directed cycle v1… v2n+1 V1 has two chords of the form (vi, vi+2). This is stronger than a result of Galeana‐Sanchez.