bluuebunny/crossref_metadata_2025_split huggingface dataset:
On Whitney's 2‐isomorphism theorem for graphs
Authors: Truemper K. 
Published: May 2007

AbstractLet G and H be 2‐connected 2‐isomorphic graphs with n nodes. Whitney's 2‐isomorphism theorem states that G may be transformed to a graph G* isomorphic to H by repeated application of a simple operation, which we will term “switching”. We present a proof of Whitney's theorem that is much shorter than the original one, using a graph decomposition by Tutte. The proof also establishes a surprisingly small upper bound, namely n‐2, on the minimal number of switchings required to derive G* from G. The bound is sharp in the sense that for any integer N there exist graphs G and H with n ≥ N nodes for which the minimal number of switchings is n‐2.
Subgraphs smaller than the girth
Authors: Simoncini Luca , Taylor Herbert 
Published: May 2007

AbstractFor graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k‐node tree T, then for every k‐node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.
Note on a new coloring number of a graph
Authors: Horák P. , Širáň J. 
Published: May 2007

AbstractThe distance coloring number Xd(G) of a graph G is the minimum number n such that every vertex of G can be assigned a natural number m ≤ n and no two vertices at distance i are both assigned i. It is proved that for any natural number n there exists a graph G with Xd(G) = n.
On the crossing numbers of products of cycles and graphs of order four
Authors: Beineke Lowell W. , Ringeisen Richard D. 
Published: May 2007

AbstractThe main results are that the crossing number of the product C4 × Cn is 2n for n ≥ 4 and that of the product K4 × Cn is 3n for n ≥ 3. These are extensions of an earlier result giving the crossing number of C3 × Cn as n for n ≥ 3.
A determination of the toroidal k‐metacyclic groups
Authors: Gross Jonathan L. , Lomonaco Samuel J. 
Published: May 2007

AbstractKronecker studied a class of groups 〈p, p ‐ 1, r〉, whose commutator subgroups are prime cyclic of order p, and whose commutator quotient groups are cyclic of order p ‐ 1. These are now commonly called the K‐metacyclic groups. It follows from the classical work of Maschke that none of the K‐metacyclic groups except 〈3, 2, 2〉 has a planar Cayley graph. It is proved here that only for p = 5 and p = 7 is a K‐metacyclic group 〈p, p ‐ 1, r〉 toroidal. To achieve this result, this paper develops a methodology for using Proulx's classification of toroidal groups by presentation to determine whether an explicitly given group is toroidal.
Two sets of graceful graphs
Authors: Delorme Charles 
Published: May 2007

AbstractWe give graceful numberings to the following graphs: (a) the union of n K4 having one edge in common, in other words the join of K2 and the union of n disjoint K2 and (b) the union of n C4 having one edge in common, in other words the product of K2 and K1,n, with n + 1 not a multiple of 4.
On a conjecture on maximal planar sequences
Authors: Fanelli Stefano 
Published: May 2007

AbstractLet d1 d2 dp denote the nonincreasing sequence d1, …, d1, d2, …, d2, …, dp, …, dp, where the term di appears ki times (i = 1, 2, …, p). In this work the author proves that the maximal 2‐sequences: 7361515, 7561517, 7761519 are planar graphical, in contrast to a conjecture by Schmeichel and Hakimi.
Hypotraceable digraphs
Authors: Grötschel Martin , Thomassen Carsten , Wakabayashi Yoshiko 
Published: May 2007

AbstractA hypotraceable digraph is a digraph D = (V, E) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which D ‐ v is traceable for all ve ∈ V. We prove that a hypotraceable digraph of order n exists iff n ≥ 7 and that for each k ≥ 3 there are infinitely many hypotraceable oriented graphs with a source and a sink and precisely k strong components. We also show that there are strongly connected hypotraceable oriented graphs and that there are hypotraceable digraphs with precisely two strong components one of which is a source or a sink. Finally, we prove that hypo‐Hamiltonian and hypotraceable digraphs may contain large complete subdigraphs.
Medians of arbitrary graphs
Authors: Slater Peter J. 
Published: May 2007

AbstractFor each vertex u in a connected graph H, the distance of u is the sum of the distances from u to each of the vertices v of H. A vertex of minimum distance in H is called a median vertex. It is shown that for any graph G there exists a graph H for which the subgraph of H induced by the median vertices is isomorphic to G.
On the number of cycles of length 4 in a maximal planar graph
Authors: Alameddine Ahmad Fawzi 
Published: May 2007

AbstractLet p and C4 (G) be the number of vertices and the number of 4‐cycles of a maximal planar graph G, respectively. Hakimi and Schmeichel characterized those graphs G for which C4 (G) = 1/2(p2 + 3p ‐ 22). This characterization is correct if p ≥ 9. However, for p = 7 or 8, there is exactly one other graph which violates the theorem in the sense that the upper bound of C4 (G) is also attained.
On the edge‐coloring problem for a class of 4‐regular maps
Authors: Jaeger F. , Shank H. 
Published: May 2007

AbstractA (plane) 4‐regular map G is called C‐simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ (G) is the smallest integer k such that the curves of G can be colored with k colors in such a way that no two curves of the same color intersect. We prove that if σ (G) ≤ 4, G is edge colorable with 4 colors. Moreover we show that a similar result for maps G with σ(G) ≤ 5 would imply the Four‐Color Theorem.
Quadrilateral embeddings of bipartite graphs
Authors: Anderson Ian 
Published: May 2007

AbstractCurrent graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions of Kn and Kn, n into graphs with quadrilateral embeddings are discussed, and some thickness results are obtained. Some new genus results are also obtained.
On graphs containing a given graph as center
Authors: Buckley Fred , Miller Zevi , Slater Peter J. 
Published: May 2007

AbstractWe examine the problem of embedding a graph H as the center of a supergraph G, and we consider what properties one can restrict G to have. Letting A(H) denote the smallest difference ∣V(G)∣ ‐ ∣V(H)∣ over graphs G having center isomorphic to H it is demonstrated that A(H) ≤ 4 for all H, and for 0 ≤ i ≤ 4 we characterize the class of trees T with A(T) = i. for n ≥ 2 and any graph H, we demonstrate a graph G with point and edge connectivity equal to n, with chromatic number X(G) = n + X(H), and whose center is isomorphic to H. Finally, if ∣V(H)∣ ≥ 9 and k ≥ ∣V(H)∣ + 1, then for n sufficiently large (with n even when k is odd) we can construct a k‐regular graph on n vertices whose center is isomorphic to H.
On Graphs Without Multicliqual Edges
Authors: Chong‐Keang Lim , Yee‐Hock Peng 
Published: May 2007

AbstractAn edge which belongs to more than one clique of a given graph is called a multicliqual edge. We find a necessary and sufficient condition for a graph H to be the clique graph of some graph G without multicliqual edges. We also give a characterization of graphs without multicliqual edges that have a unique critical generator. Finally, it is shown that there are infinitely many self‐clique graphs having more than one critical generator.
Exceptional trivalent cayley graphs for dihedral groups
Authors: Powers David L. 
Published: May 2007

AbstractIf n is divisible by at least three distinct primes, the dihedral group Dn can be generated by three nonredundant, involuntary elements. We study the Cayley graphs resulting from such a presentation of Dn for several families of n and for all admissible n < 120. All these graphs are trivalent, bipartite, Hamiltonian, of girth 6, and are regular representations of their groups. For each n, the isomorphism classes are determined and the graphs are described by a simple code.
On one‐factorizations of compositions of graphs
Authors: Himelwright P. , Wallis W. D. , Williamson J. E. 
Published: May 2007

AbstractLet G[H] denote the composition of the graphs G and H. If G can be decomposed into one‐factors and two‐factors, H can be decomposed into one‐factors, and H is not the empty graph on an odd number of vertices, then G[H] can be decomposed into one‐factors.
On digraphs without antidirected cycles
Authors: Grant Douglas D. , Jaeger F. , Payan C. 
Published: May 2007

AbstractLet t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n − 1)] ≤ t(n) ≤ 1/2 (n − 1) for n ≥ 5. Let tr (n) denote the corresponding quantity for r‐colorable digraphs. We show that [16/5(n − 1)] ≤ t5(n) ≤ t6(n) ≤ 10/3(n − 1) for n ≥ 5 and that t4(n) = 3(n − 1) for n ≥ 3.
Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable
Authors: Thomason Andrew 
Published: May 2007

AbstractThe generalized Petersen graph P(6k + 3, 2) has exactly 3 Hamiltonian cycles for k ≥ 0, but for k ≥ 2 is not uniquely edge colorable. This disproves a conjecture of Greenwell and Kronk [1].
The bandwidth problem for graphs and matrices—a survey
Authors: Chinn P. Z. , Chvátalová J. , Dewdney A. K. , Gibbs N. E. 
Published: May 2007

AbstractThe bandwidth problem for a graph G is to label its n vertices vi with distinct integers f(vi) so that the quantity max{| f(vi) − f(vi)| : (vi vj) ∈ E(G)} is minimized. The corresponding problem for a real symmetric matrix M is to find a symmetric permutation M' of M so that the quantity max{| i − j| : m'ij ≠ 0} is minimized. This survey describes all the results known to the authors as of approximately August 1981. These results include the effect on bandwidth of local operations such as refinement and contraction of graphs, bounds on bandwidth in terms of other graph invariants, the bandwidth of special classes of graphs, and approximate bandwidth algorithms for graphs and matrices. The survey concludes with a brief discussion of some problems related to bandwidth.
Distribution of points by degree and orbit size in a large random tree
Authors: Bailey C. K. 
Published: May 2007

AbstractUsing generating functions and asymptotic techniques, the probability that in a large random tree a point is of degree r and an orbit of size s for r ≤ 7 and s ≤ 7 is calculated. For example, it is found that about 17% of the points of a random tree are fixed and have degree one. This method is readily applied to different types of trees.
Orientations of circle graphs
Authors: Read R. C. , Rotem D. , Urrutia J. 
Published: May 2007

AbstractLet C(v1, …,vn) be a system consisting of a circle C with chords v1, …,vn on it having different endpoints. Define a graph G having vertex set V(G) = {v1, …,vn} and for which vertices vi and vj are adjacent in G if the chords vi and vj intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v1, …,vn) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v1, …,vn) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.
Bipartite graphs with cycles of all even lengths
Authors: Schmeichel Edward , Mitchem John 
Published: May 2007

AbstractLet G = (X, Y, E) be a bipartite graph with X = Y = n. Chvátal gave a condition on the vertex degrees of X and Y which implies that G contains a Hamiltonian cycle. It is proved here that this condition also implies that G contains cycles of every even length when n > 3.
A survey of bounds for classical Ramsey numbers
Authors: Chung F. R. K. , Grinstead C. M. 
Published: May 2007

AbstractThis paper is a survey of the methods used for determining exact values and bounds for the classical Ramsey numbers in the case that the sets being colored are two‐element sets. Results concerning the asymptotic behavior of the Ramsey functions R(k,l) and Rm(k) are also given.
Ramsey theory for graph connectivity
Authors: Matula David W. 
Published: May 2007

Abstractrc(k) Denotes the smallest integer such that any c‐edge‐coloring of the rc(k) vertex complete graph has a monochromatic k‐connected subgraph. For any c, k ≧ 2, we show 2c(k – 1) + 1 ≦ rc(k) < 10/3 c(k – 1) + 1, and further that 4(k – 1) + 1 ≧ r2(k) < (3 + √ (k – 1) + 1. Some exact values for various Ramsey connectivity numbers are also computed.
On sequential labelings of graphs
Authors: Grace Thom 
Published: May 2007

AbstractA valuation on a simple graph G is an assignment of labels to the vertices of G which induces an assignment of labels to the edges of G. β‐valuations, also called graceful labelings, and α‐valuations, a subclass of graceful labelings, have an extensive literature; harmonious labelings have been introduced recently by Graham and Sloane. This paper introduces sequential labelings, a subclass of harmonious labelings, and shows that any tree admitting an α‐valuation also admits a sequential labeling and hence is harmonious. Constructions are given for new families of graceful and sequential graphs, generalizing some earlier results. Finally, a conjecture of Frucht is shown to be wrong by exhibiting several graceful labelings of wheels in which the center label is larger than previously thought possible.
The number of connected sparsely edged graphs. IV large nonseparable graphs
Authors: Wright E. M. 
Published: May 2007

AbstractThe number of nonseparable graphs on n labeled points and q lines is u(n, q). In the second paper of this series an exact formula for u(n, n + k) was found for general n and successive (small) k. The method would give an asymptotic approximation for fixed k as n → ∞. Here an asymptotic approximation to u(n, n + k) is found when k = O(n1/2) and an approximation to logu(n, n + k) when k < (1 ‐ ϵ)(1/3 n)1/2. The problem of finding an approximation to u(n, q) when (q ‐ n)/n1/2 → + → and q/n ‐ 1/2 logn ‐ 1/2 log logn → ‐ ∞ is open.
Integer flows
Authors: Younger D. H. 
Published: May 2007

AbstractA k‐flow is an assignment of edge directions and integer weights in the range 1, …., k – 1 to the edges of an undirected graph so that ateach vertex the flow in is equal to the flow out. This paper gives a polynomial algorithm for finding a 6‐flow that applies uniformly to each graph. The algorithm specializes to give a 5‐flow for planar graphs.
On a product dimension of bipartite graphs
Authors: Poljak S. , Rödl D. , Pultr A. 
Published: May 2007

AbstractA product dimension of bipartite graphs bid G analogous to the Dushnik‐Miller dimension of posets and to the dimension of general symmetric graphs is studied. It is shown that bidG ≦ 1/2|V(G)| + 1 and almost all bipartite graphs G have bidG close to 1/2|V(G)|. On the other hand it is shown to be considerably less for everyday graphs like trees, cycles, cubes, etc.
On the sum of all distances in a graph or digraph
Authors: Plesník Ján 
Published: May 2007

AbstractThe transmission of a graph or digraph G is the sum of all distances in G. Strict bounds on the transmission are collected and extended for several classes of graphs and digraphs. For example, in the class of 2‐connected or 2‐edge‐connected graphs of order n, the maximal transmission is realized only by the cycle Cn. The independence of the transmission on the diameter or radius is shown. Remarks are also given about the NP‐hardness of some related algorithmic problems.
Subdivisions of graphs with large minimum degree
Authors: Thomassen Carsten 
Published: May 2007

AbstractWe prove a theorem on path systems implying the conjecture of Bollobás that there exists a function f(k, m) (where k and m are natural numbers) satisfying the following: For each graph G of minimum degree at least f(k, m) there exists a graph H of minimum degree at least k such that G contains the graph obtained from H by subdividing each edge m times.
Recognizing decomposable graphs
Authors: Chvátal V. 
Published: May 2007

AbstractA graph is called decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We point out a simple and efficient algorithm for recognizing decomposable graphs with maximum degree at most 3 and prove that recognizing decomposable graphs with maximum degree 4 is an NP‐complete problem.
Factors and factorizations of graphs—a survey
Authors: Akiyama Jin , Kano Mikio 
Published: May 2007

AbstractA degree factor of a graph is either an r‐factor (regular of degree r) or an [m, n]‐factor (with each degree between m and n). In a component factor, each component is a prescribed graph. Both kinds of factors are surveyed, and also corresponding factorizations.
Almost‐regular factorization of graphs
Authors: Akiyama Jin , Kano Mikio 
Published: May 2007

AbstractFor integers a and b, 0 ⩽ a ⩽ a ⩽ b, an [a, b]‐graph G satisties a ⩽ deg(x, G) ⩽ b for every vertex x of G, and an [a, b]‐factor is a spanning subgraph F such that a ⩽ deg(x, F) ⩽ b for every vertex x of F. An [a, b]‐factor is almost‐regular if b = a + 1. A graph is [a, b]‐factorable if its edges can be decomposed into [a, b]‐factors. When both K and t are positive integers and s is a nonnegative integer, we prove that every [(12K + 2)t + 2ks, (12k + 4)t + 2ks]‐graph is [2k,2k + 1]‐factorable. As its corollary, we prove that every [r.r + 1]‐graph with r ⩾ 12k2 + 2k is [2k + 1]‐factorable, which is a partial extension of the two results, one by Thomassen and the other by Era.
Almost reconstructing infinite, rayless graphs
Authors: Schmidt Rüdiger 
Published: May 2007

AbstractWe show that for every infinite, rayless graph G the following holds. If G is hypomorphic to H then G is isomorphic to an induced subgraph of G. This proves a conjecture of R. Halin for the class of infinite, rayless graphs and partly extends a result of Bondy and Hemminger. The proof makes use of the structure theory for rayless graphs which was developed by the author in a previous paper.
Extremal graphs of diameter at most 6 after deleting any vertex
Authors: Usami Yoko 
Published: May 2007

AbstractSuppose G is a graph of n vertices and diameter at most d having the property that, after deleting any vertex, the resulting subgraph has diameter at most 6. Then G contains at least max{n, (4n ‐ 8)/3} edges if 4 ≤ d ≤ 6.
Large bipartite graphs with given degree and diameter
Authors: Delorme C. 
Published: May 2007

AbstractWe give constructions of bipartite graphs with maximum Δ, diameter D on B vertices, such that for every D ≥ 2 the lim infΔ→∞B. Δ1‐D = bD > 0. We also improve similar results on ordinary graphs, for example, we prove that limΔ→∞N · Δ−D = 1 if D is 3 or 5. This is a partial answer to a problem of Bollobás.
Arc transitive covering digraphs and their eigenvalues
Authors: Babai L. 
Published: May 2007

AbstractWe prove that every finite regular digraph has an arc‐transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2‐arc‐transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex‐transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc‐transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc‐transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2‐arc‐transitive graphs X.
Lengths of cycles in halin graphs
Authors: Bondy J. A. , Lovász L. 
Published: May 2007

AbstractA Halin graph is a plane graph H = T U C, where T is a plane tree with no vertex of degree two and at least one vertex of degree three or more, and C is a cycle connecting the endvertices of T in the cyclic order determined by the embedding of T. We prove that such a graph on n vertices contains cycles of all lengths l, 3 ≤ l n, except, possibly, for one even value m of l. We prove also that if the tree T contains no vertex of degree three then G is pancyclic.
The graph reconstruction number
Authors: Harary Frank , Plantholt Michael 
Published: May 2007

AbstractThe reconstruction number of graph G is the minimum number of point‐deleted subgraphs required in order to uniquely identify the original graph G. We list, based on computer calculations, the reconstruction number for all graphs with at most seven points. Some constructions and conjectures for graphs of higher order are given. the most striking statement is our concluding conjeture that almost all graphs have have reconstruction number three.
Classes of interval graphs under expanding length restrictions
Authors: Fishburn P. C. , Graham R. L. 
Published: May 2007

AbstractLet C(α) denote the finite interval graphs representable as intersection graphs of closed real intervals with lengths in [1, α]. The points of increase for C are the rational α ≥ 1. The set D(α) = [∩β>αC(β)]\C(α) of graphs that appear as soon as we go past α is characterized up to isomorphism on the basis of finite sets E(α) of irreducible graphs for each rational α. With α = p/q and p and q relatively prime, ∣E(α)∣ is computed for all (p,q) with q ⩽ 2 and p = q + 1. When q = 1, E(p) contains only the bipartite star K1, p+2. A lowr bound on ∣E(α)∣ is given for all rational α.
Some conditions for the existence of f‐factors
Authors: Katerinis P. 
Published: May 2007

AbstractLet m, l, n be three odd integers such that m > l > n. It is proved that if a graph G has an m‐factor and an n‐factor, then it also has an l‐factor. In addition, we obtain sufficient conditions for the existence of an f‐factor, in terms of vertex‐deleted subgraphs.
Minimum k‐hamiltonian graphs, II
Authors: Paoli M. , Wong W. W. , Wong C. K. 
Published: May 2007

AbstractWe consider in this paper graphs which remain hamiltonian after the removal of k edges (k‐edge hamiltonian) or k vertices (k‐hamiltonian). These classes of graphs arise from reliability considerations in network design. In a previous paper, W. W. Wong and C. K. Wong presented families of minimum k‐hamiltonian graphs and minimum k‐edge hamiltonian graphs for k even. Here, we complete this study in the case where k is odd.
On the domination of the products of graphs II: Trees
Authors: Jacobson Michael S. , Kinch Lael F. 
Published: May 2007

AbstractFor a graph G, a subset of vertices D is a dominating set if for each vertex X not in D, X is adjacent to at least one vertex of D. The domination number, γ(G), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H,

One result presented in this paper settles this question in the case when at least one of G or H is a tree. We show that

for all graphs G and any tree T.Furthermore, we supply a partial characterization for which pairs of trees, T1 and T2, strict inequality occurs. We show

for almost all pairs of trees.