bluuebunny/crossref_metadata_2025_split huggingface dataset:
Generalized Embedding Schemes
Authors: Stahl Saul 
Published: May 2007

AbstractCovering projections are used to provide a logical foundation for the generalized embedding schemes which describe embeddings of graphs on closed surfaces that are not necessarily orientable. Criteria are provided to resolve the question of when such schemes describe the same embedding, and when that embedding is orientable. The schemes are then applied to derive some interpolation‐type theorems for embeddings on closed surfaces.
The genus of the n‐octahedron: Regular cases
Authors: Jungerman Mark , Ringel Gerhard 
Published: May 2007

AbstractThe n‐octahedron On, also denoted K(2,2, …, 2) or Kn(2), is the complete n‐partite graph with two vertices in each partite set. The formula

for the (orientable) genus of On is conjectured for all n and proved for n ≠ (mof 3). Triangular embeddigns are possible precisely when n ≠ 2 (mod 3), and the formula is established by exhibiting such embeddings.
A class of Hamiltonian regular graphs
Authors: Erdös Paul , Hobbs Arthur M. 
Published: May 2007

AbstractIn this paper, we show that n ⩾ 4 and if G is a 2‐connected graph with 2n or 2n−1 vertices which is regular of degree n−2, then G is Hamiltonian if and only if G is not the Petersen graph.
Centers to centroids in graphs
Authors: Slater Peter J. 
Published: May 2007

AbstractFor S ⊆ V(G) the S‐center and S‐centroid of G are defined as the collection of vertices u ∈ V(G) that minimize es(u) = max {d(u, v): v ∈ S} and ds(u) = ∑u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ⩽ k ⩽|V(G)| and u ∈ V(G) let rk(u) = max {∑s∈S d(u, s): S ⊆ V(G), |S| = k}. The k‐centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which rk(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.
Current graphs and bi‐embeddings
Authors: Anderson I. , White A. T. 
Published: May 2007

AbstractLet N(γ,γ′) denote the size of the smallest complete graph which cannot be edge‐partitioned into two parts embeddable in closed orientable surfaces of genera γ,γ′ respectively. The theory of current graphs is used to determine the values of N(γ,γ′) in certain cases. Some related block designs are discussed.
Degree frequencies in digraphs and tournaments
Authors: Alspach Brian , Reid K. B. 
Published: May 2007

AbstractThe number of vertices in a digraph G having a particular outdegree (indegree) is called the frequency of the outdegree (indegree). A set F of distinct positive integers {f1, f2, …, fn} is the frequency set of the digraph G if every outdegree and indegree occurs with frequency fj∈F and for each fj∈F there is a least one outdegree and at least one indegree with frequency fj. We prove that each nonempty set F of positive integers is the frequency set of some tournament, and we determine the smallest possible order for such a tournament. Similar results for asymmetric digraphs are also given. The results and techniques for frequency sets are used to derive corresponding results for vertex frequency partitions.
On supercompact graphs
Authors: Lim Chong‐Keang 
Published: May 2007

AbstractA graph G is called a supercompact graph if G is the intersection graph of some family 𝒯 of subsets of a set X such that 𝒯 satisfies the Helly property and for any x≠y in X, there exists S ∈ 𝒯 with x ∈ S, y ∉ S. Various characterizations of supercompact graphs are given. It is shown that every clique‐critical graph is supercompact. Furthermore, for any finite graph, H, there is at most a finite number of different supercompact graphs G such that H is the clique‐graph of G.
Fixed‐edge theorem for graphs with loops
Authors: Nowakowski Richard , Rival Ivan 
Published: May 2007

AbstractLet G be an undirected graph without multiple edges and with a loop at every vertex—the set of edges of G corresponds to a reflexive and symmetric binary relation on its set of vertices. Then every edge‐preserving map of the set of vertices of G to itself fixes an edge [{f(a), f(b)} = {a, b} for some edge (a, b) of G] if and only if (i) G is connected, (ii) G contains no cycles, and (iii) G contains no infinte paths. The proof is conerned with those subgraphs H of a graph G for which there is an edge‐preserving map f of the set of vertices of G onto the set of vertices of H and satisfying f(a) = a for each vertex a of H.
Theorem on directed graphs, applicable to logic
Authors: Shoesmith D. J. , Smiley T. J. 
Published: May 2007

AbstractA semicycle is said to turn at a point a if the arcs incident to a are both to it or both from it. We prove that if a nonempty set of points of a finite directed graph contains a turning point of each semicycle, then one of its members is a turning point of every semicycle to which it belongs; and we indicate the application of this result to mathematical logic through the modeling of arguments by graphs.
Spectral criterion for cycle balance in networks
Authors: Acharya B. Devadas 
Published: May 2007

AbstractA network is cycle balanced if the product of the weights (nonzero real numbers) of the lines of every cycle in it is positive. In this paper, we prove that a network D is cycle balanced if and only if its adjacency matrix is isospectral with its nonnegative counterpart. Consequent to this theorem is an analogous criterion for structural balance in sigraphs (abbreviation for “signed graphs”) as also for cycle balance in signed digraphs. These criteria establish in a natural way a wide scope for cospectrality considerations in the classes of signed digraphs and sigraphs.
Genus of cartesian products of regular bipartite graphs
Authors: Pisanski Tomaž 
Published: May 2007

AbstractLet G(n, d) denote a connected regular bipartite graph on 2n vertices and of degree d. It is proved that any Cartesian product G(n, d) × G1(n1, d1) × G2(n2, d2) × ⃛ × Gm(nm, dm), such that max {d1, d2,…, dm} ≤ d ≤ d1 + d2 + ⃛ + dm, has a quadrilateral embedding, thereby establishing its genus, and thereby generalizing a result of White. It is also proved that if G is any connected bipartite graph of maximum degree D, if Qm is the m‐cube graph, and if m ≥ D then G × Qm has a quadrilateral embedding.
Bigraphs versus digraphs via matrices
Authors: Brualdi Richard A. , Harary Frank , Miller Zevi 
Published: May 2007

AbstractIt was observed by Dulmage and Mendelsohn in their work on matrix reducibility that there is a one‐to‐one correspondence between bigraphs and digraphs determined by the utilization of the adjacency matrix. In this semiexpository paper we explore the interaction between this correspondence and a theory of matrix decomposability that is developed in several different articles. These results include: (a) a characterization of those bipartite graphs that can be labeled so that the resulting digraph is symmetric; (b) a criterion for the bigraph of a symmetric digraph to be connected; (c) a necessary and sufficient condition for a square binary matrix to be fully indecomposable in terms of its associated bigraph, and (d) matrix criteria for a digraph to be strongly, unilaterally, or weakly connected. We close with an unsolved extermal problem on the number of components of the bigraph of various orientations of a given graph. This leads to new amusing characterizations of trees and bigraphs.Dedicated to the graph‐theoretic partnership of Lloyd Dulmage and Nathan Mendelsohn.
An upper bound for the path number of a graph
Authors: Donald Alan 
Published: May 2007

AbstractThe path number of a graph G, denoted p(G), is the minimum number of edge‐disjoint paths covering the edges of G. Lovász has proved that if G has u odd vertices and g even vertices, then p(G) ≤ 1/2 u + g ‐ 1 ≤ n ‐ 1, where n is the total number of vertices of G. This paper clears up an error in Lovász's proof of the above result and uses an extension of his construction to show that p(G) ≤ 1/2 u + [3/4g] ≤ [3/4n].
Realizability of p‐point graphs with prescribed minimum degree, maximum degree, and line connectivity
Authors: Boesch F. T. , Suffel C. L. 
Published: May 2007

AbstractIt is well known that certain graph‐theoretic extremal questions play a central role in the study of communication network vulnerability. Herein we consider a generalization of some of the classical results in this area. We define a (p, Δ, δ, λ) graph as a graph having p points, maximum degree Δ, minimum degree Δ, and line connectivity λ. An arbitrary quadruple of integers (a, b, c, d) is called (p, Δ, δ, λ) realizable if there is a (p, Δ, δ, λ) graph with p = a, Δ = b, Δ = c, and λ = d. Necessary and sufficient conditions for a quadruple to be (p, Δ, δ, λ) realizable are derived.
The number of connected sparsely edged graphs. III. Asymptotic results
Authors: Wright E. M. 
Published: May 2007

AbstractThe number of connected graphs on n labeled points and q lines (no loops, no multiple lines) is f(n,q). In the first paper of this series I showed how to find an (increasingly complicated) exact formula for f(n,n+k) for general n and successive k. The method would give an asymptotic approximation to f(n,n+k) for any fixed k as n → ∞. Here I find this approximation when k = o(n1/3), a much more difficult matter. The problem of finding an approximation to f(n,q) when q > n + Cn1/3 and (2 q/n) ‐ log n → ‐ ∞ is open.
Matchings and walks in graphs
Authors: Godsil C. D. 
Published: May 2007

AbstractThe matching polynomial α(G, x) of a graph G is a form of the generating function for the number of sets of k independent edges of G. in this paper we show that if G is a graph with vertex v then there is a tree T with vertex w such that \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{\alpha (G\backslash v, x)}}{{\alpha (G, x)}} = \frac{{\alpha (T\backslash w, x)}}{{\alpha (T, x)}}. $\end{document}This result has a number of consequences. Here we use it to prove that α(G\v, 1/x)/xα(G, 1/x) is the generating function for a certain class of walks in G. As an application of these results we then establish some new properties of α(G, x).
Some arrowing results for trees versus complete graphs
Authors: Polimeni Albert D. , Straight H. JosephS , Yellen Jay 
Published: May 2007

AbstractFor an arbitrary tree T of order m and an arbitrary positive integer n, Chvátal proved that the Ramsey number r(T, Kn) = 1 + (m − 1) (n − 1). for graphs G, G1, and G2, we say that G arrows G1 and G2, written G → (G1, G2), if for every factorization G = R ⊕ B, either G1 is a subgraph of R or G2 is a subgraph of B. it is shown that (i) for each l ≥ 2, K1+ (m−1)(n−1) −E(K1) → (T, Kn) for m ≥ 2/ − 1 and n ≥ 2; (ii) K1 +,(m −1)(n −1) − E(H) → (T, Kn), where H is any tree of order m − 1, m ≥ 3 and n ≥ 2. It is further shown that result (i) is sharp with respect to the inequality m ≥ 2/− 1; in particular, examples are given to show that K1 + (2l−3)(n−1) E(K1) ↛ (P21−2, Kn) for all n ≥ 2, where P21−2 denotes the path of order 21 − 2. Also result (ii) is sharp with respect to the order of H; examples aregiven to show that K1 + (m−1)(n−1)− E(K(1, m − 1)) ↛(T, Kn)for any tree T of order m and any n ≥ 2.
Which rational numbers are binding numbers?
Authors: Kane V. G. , Mohanty S. P. , Straus E. G. 
Published: May 2007

AbstractThe concept of the binding number of a graph was introduced by Woodall in 1973. in this paper we characterize the set Fn of all pairs (a, b) of integers such that there is a graph G with n vertices and binding number a/b that has a realizing set of b vertices.
Generalized line graphs
Authors: Cvetkovic̀ Dragoš , Doob Michael , Simic̀ Slobodan 
Published: May 2007

AbstractGeneralized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation and construction of the 31 minimal nongeneralized line graphs, a Krausz‐type covering characterization, and Whitney‐type theorems on isomorphisms and automorphisms.
Paley graphs satisfy all first‐order adjacency axioms
Authors: Blass Andreas , Exoo Geoffrey , Harary Frank 
Published: May 2007

AbstractA graph satisfies Axiom n if, for any sequence of 2n of its points, there is another point adjacent to the first n and not to any of the last n. We show that, for each n, all sufficiently large Paley graphs satisfy Axiom n. From this we conclude at once that several properties of graphs are not first order, including self‐complementarity and regularity.
Domination‐balanced graphs
Authors: Payan Charles , Xuong Nguyen Huy 
Published: May 2007

AbstractA set D of vertices in a graph is said to be a dominating set if every vertex not in D is adjacent to some vertex in D. The domination number β(G) of a graph G is the size of a smallest dominating set. G is called domination balanced if its vertex set can be partitioned into β(G) subsets so that each subset is a smallest dominating set of the complement G of G. The purpose of this paper is to characterize these graphs.
Note on the reconstruction of infinite graphs with a fixed finite number of components
Authors: Andreae Thomas 
Published: May 2007

AbstractFor every positive integer c, we construct a pair Gc, Hc of infinite, nonisomorphic graphs both having exactly c components such that Gc and Hc are hypomorphic, i.e., Gc and Hc have the same families of vertex‐deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G1, H1 is an example for a pair of non‐isomorphic, hypomorphic, connected graphs also having connected complements—a property not shared by any of the previously known counterexamples to the reconstruction conjecture for infinite graphs.
On the toroidal thickness of graphs
Authors: Anderson Ian 
Published: May 2007

AbstractThe toroidal thickness t1(G) of a graph G is the minimum value of k such that G is the union of k graphs each of which is embeddable on a torus. We find t1(Gm), where Gm is the graph obtained from the complete graph Km by removing a Hamiltonian cycle, and we show that t1(Kn(3)) = [1/2n] for many values of n. The method of approach involves the construction of sets of triples related to Skolem triples.
4‐valent graphs
Authors: Enns T. C. 
Published: May 2007

AbstractLet {pk}k≥2, k≠4 be a sequence of non‐negative integers which satisfies 8 + Σk≥3(k — 4)pk = 0. Then there exists an integer p4 such that there exists a 2‐connected planar graph with exactly pk k‐gons as faces for all k ≥ 2. This paper determines all such p4 when pk = 0 for k ≥ 5 and determines that there is a constant C ≥ 1 such that for some m ≤ p2 + 1/4p3 + C, there exists a 2‐connected planar graph with exactly pk faces for each p4 = m + 2w, w a positive integer. When there exists at least one odd k ≥ 3 for which pk ≠ 0, the coefficient 2 of w in the above equation may be replaced by 1. These conclusions do not hold if the coefficients of p2 and p3 are any smaller than 1 and 1/4, respectively.
More rotation numbers for complete bipartite graphs
Authors: Bollobás Béla , Cockayne E. J. 
Published: May 2007

AbstractLet G be a simple undirected graph which has p vertices and is rooted at x. Informally, the rotation number h(G, x) of this rooted graph is the minimum number of edges in a p vertex graph H such that for each vertex v of H, there exists a copy of G in H with the root x at v. In this article we calculate some rotation numbers for complete bipartite graphs, and thus greatly extend earlier results of Cockayne and Lorimer.
Randomly antitraceable digraphs
Authors: Fink John Frederick 
Published: May 2007

AbstractAn antipath in a digraph is a semipath containing no (directed) path of length 2. A digraph D is randomly antitraceable if for each vertex v of D, any antipath beginning at v can be extended to a hamiltonian antipath beginning at v. In this paper randomly antitraceable digraphs are characterized.
On 4‐cycles in random bipartite tournaments
Authors: Bollobés Béla , Frank Ove , KarońSki Michał 
Published: May 2007

AbstractWe consider a random m by n bipartite tournament Tmn consisting of mn independent random arcs which have a common probability p of being directed from the m part to the n part. We determine the expected value and variance of the number of 4‐cycles in Tmn and the probability that Tmn has no cycles. An asymptotic expression for this probability is also given when p = 1/2 and m and n tend to infinity.
On the genus of five‐ and six‐regular graphs
Authors: Proulx Viera Krňanová 
Published: May 2007

AbstractThis paper shows how to construct infinitely many regular graphs of degrees five and six having given genus γ > 0, which settles favorably Conjecture 1 stated by T. W. Tucker. Tucker has shown that there are infinitely many regular graphs of degrees four and three of arbitrary given genus (Theorem 1). He also proved that the number of regular graphs of degree greater than six embeddable in a given surface is finite (Corollary to Proposition 1). The case of the regular graphs of degrees six and five was left unanswered (Conjecture 1). This paper also shows a new way of constructing infinitely many regular graphs of degrees three and four of arbitrary genus γ > 0.
Graph decomposition with applications to subdivisions and path systems modulo k
Authors: Thomassen Carsten 
Published: May 2007

AbstractThe existence of a function α(k) (where k is a natural number) is established such that the vertex set of any graph G of minimum degree at least α(k) has a decomposition A ∪ B ∪ C such that G(A) has minimum degree at least k, each vertex of A is joined to at least k vertices of B, and no two vertices of B are separated by fewer than k vertices in G(G ∪ C). This is applied to prove the existence of subdivisions of complete bipartite graphs (complete graphs) with prescribed path lengths modulo k in graphs of sufficiently high minimum degree (chromatic number) and path systems with prescribed ends and prescribed lengths modulo k in graphs of sufficiently high connectivity.
Packing graphs with odd and even trees
Authors: Fishburn P. C. 
Published: May 2007

AbstractThe Gyárfás‐Lehel tree‐packing conjecture asserts that any sequence T1, T2, …, Tn−1 of trees with 1, 2, …, n ‐ 1 edges packs into the complete graph Kn on n vertices. The present paper examines two conjectures that jointly imply the Gyárfás‐Lehel conjecture: 1. For n even, any T1, T3, …, Tn−1 pack into the half‐complete graph Hn on n vertices.2. For n odd, any T2, T4, …, Tn−1 pack into the half‐complete graph Hn on n vertices.The Hn are uniquely defined by their degree sequences: Hn and Hn+1 are complements in Kn+1. It is shown that Hn and Tn+1 pack into Hn+2 if Tn+1 is a double star, unimodal triple star, interior‐3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n ≤ 9, so that the Gyárfás‐Lehel conjecture holds for n ≤ 9.
Automorphism properties of embedded graphs
Authors: Hutchinson Joan P. 
Published: May 2007

AbstractThis paper presents some conditions under which every automorphism of a graph, embedded on a surface of positive genus, maps face boundaries of the embedding to face boundaries. These results extend a result of Whitney which provides an analogous, but simpler, condition for planar graphs. The new result is applied to graphs on the torus to obtain a classification of many toroidal vertex‐, edge‐, and face‐transitive graphs.
Vertex‐transitive graphs: Symmetric graphs of prime valency
Authors: Lorimer Peter 
Published: May 2007

AbstractLet G be a group acting symmetrically on a graph Σ, let G1 be a subgroup of G minimal among those that act symmetrically on Σ, and let G2 be a subgroup of G1 maximal among those normal subgroups of G1 which contain no member except 1 which fixes a vertex of Σ. The most precise result of this paper is that if Σ has prime valency p, then either Σ is a bipartite graph or G2 acts regularly on Σ or G1 | G2 is a simple group which acts symmetrically on a graph of valency p which can be constructed from Σ and does not have more vertices than Σ. The results on vertex‐transitive groups necessary to establish results like this are also included.
Enumeration by frame group and range groups
Authors: Redfield J. Howard 
Published: May 2007

AbstractWider extension is here given to the theory developed in an earlier paper, in which the enumeration of certain configurations or combinatorial entities was made to depend on two or more groups (range groups). The present paper recognizes for the first time the essential part played by an additional group, the frame group, which includes all the range groups as subgroups, and which was implicit in the earlier theory as the symmetric group of the degree of the range groups. The use of frame groups which are not symmetric greatly extends the range of application of the theory, and allows its development in terms of abstract groups. By the use of the conjugate sets of the subgroups (both cyclic and noncyclic) of the frame group, instead of merely the conjugate sets of its operations, a complete solution is obtained for the problem (solved only for special cases in the earlier paper) of determining the invariance groups admitted by the various configurations enumerated.
Factors in a class of regular digraphs
Authors: Ramanath M. V. S. 
Published: May 2007

AbstractFor the class of 2‐diregular digraphs: (1) We give a simple closed form expression—a power of 2—for the number of difactors. (2) For the adjacency matrices of these graphs, we show an intimate relationship between the permanent and determinant. (3) We give a necessary and sufficient condition for the Cartesian product of two directed circuits to have a difactor with exactly k components thereby generalizing a result of Trotter and Erdöos. Our results also show that a conjecture of Bondy, regarding vertex‐transitive graphs, fails to hold for vertex‐transitive digraphs.
Some observations on the oberwolfach problem
Authors: Alspach Brian , Häggkvist Roland 
Published: May 2007

AbstractSome results concerning decompositions of Kn, Kn ‐ F(where F denotes a 1‐factor) and complements of a family of special cubic graphs into 2‐factors of the same type are given. In particular, if 2d is a divisor of n, it is shown that Kn ‐ F can be decomposed into 2‐factors each of whose components is a cycle of length 2d.
On the chromatic number of the general Kneser‐graph
Authors: Frankl P. 
Published: May 2007

AbstractGiven integers k, n, 2 < k < n, let us define a graph with vertex set V = {F ⊂{1, 2, …, n}: ∩F = k}, and (F, F') is an edge if |F ∩ F′| ≤ 1. We show that for n > n0(k) the chromatic number of this graph is (k ‐ 1)() + rs, where n = (k ‐ 1)s + r, 0 ≤ r < k ‐ 1.
Unique and faithful embeddings of projective‐planar graphs
Authors: Negami Seiya 
Published: May 2007

AbstractA graph G is uniquely embeddable in a surface F2 if for any two embeddings f1,f2: G → F2, there exists an isomorphism σ: G → G and a homeomorphism h: F2 → F2 for which h → f1 = f2 σ. A graph G is faithfully embeddable in a surface F2 if G admits an embedding f: G → F2 such that for any isomorphism σ: G → G, there is a homeomorphism h: F2 → F2 with h → f = f → σ. It will be shown that if a projective‐planar graph G is 5‐connected and contains a subdivision of the complete graph K6 as its subgraph, then G is uniquely embeddable in a projective plane, and that moreover if G is not isomorphic to K6, then G is faithfully embeddable in a projective plane.
Do nearly balanced multigraphs have more spanning trees?
Authors: Cheng Ching‐Shui , Masaro Joseph C. , Wong Chi Song 
Published: May 2007

AbstractLetdithe degree of theith vertex of a mutigraph and λijbe the number of edges between vertexiand vertexj.A multigraph is called nearly balanced if |di−di| ≤1 for alli≠i′ and |λij−λij| for alliand allj,j′ Let be the collection of all the multigraphs withvvertices and e edges. It is shown that for anyv, there is ane* such that if, then any nearly balanced graph in ζv, ehas more spanning trees than any non‐nearly‐balanced graph in ζv, e.