bluuebunny/crossref_metadata_2025_split huggingface dataset:
Graphs with unavoidable subgraphs with large degrees
Authors: Caccetta L. , Erdös P. , Vijayan K. 
Published: June 2007

AbstractLet 𝒢(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ 𝒢 (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a Kk + 1 in terms of the number of edges in G. In this paper we prove that, for m = αn2, α > (k ‐ 1)/2k, G contains a Kk + 1, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ⌊n2/4⌋ + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn2, α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n).
A reduction method to find spanning Eulerian subgraphs
Authors: Catlin Paul A. 
Published: June 2007

AbstractWe ask, When does a graph G have a subgraph Γ such that the vertices of odd degree in Γ form a specified set S ⊆ V(G), such that G ‐ E(Γ) is connected? If such a subgraph can be found for a suitable choice of S, then this can be applied to problems such as finding a spanning eulerian subgraph of G. We provide a general method, with applications.
Pursuit—Evasion games on graphs
Authors: Chung F. R. K. , Cohen Joel E. , Graham R. L. 
Published: June 2007

AbstractTwo players, Red and Blue, each independently choose a vertex of a connected graph G. Red must then pay Blue an amount equal to the distance between the vertices chosen. In this note, we investigate the value ν(G)of this pursuit‐evasion game for various classes of graphs G, as well as those optimal mixed strategies for achieving ν(G). It is shown that some rather counterintuitive behavior can occur. For example, there exist graphs G in which, for any optimal mixed strategy, Red never selects a vertex in the center of G.
On the strong perfect graph conjecture
Authors: Olariu Stephan 
Published: June 2007

AbstractA graph G is perfect if for every induced subgraph H of G the chromatic number χ(H) equals the largest number ω(H) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement G¯ contains an odd chordless cycle of length at least 5. Its resolution has eluded researchers for more than 20 years. We prove that the conjecture is true for a class of graphs that we describe by forbidden configurations.
On the number of Hamiltonian cycles in triangulations
Authors: Kratochvil Jan , Zeps Dainis 
Published: June 2007

AbstractIt is proved that if a planar triangulation different from K3 and K4 contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [2], this yields that, for n ⩾ 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar triangulation on n vertices is four. We also show that this theorem holds for triangulations of arbitrary surfaces and for 3‐connected triangulated graphs.
On‐line and first fit colorings of graphs
Authors: Gyárfás A. , Lehel J. 
Published: June 2007

AbstractA graph coloring algorithm that immediately colors the vertices taken from a list without looking ahead or changing colors already assigned is called “on‐line coloring.” The properties of on‐line colorings are investigated in several classes of graphs. In many cases we find on‐line colorings that use no more colors than some function of the largest clique size of the graph. We show that the first fit on‐line coloring has an absolute performance ratio of two for the complement of chordal graphs. We prove an upper bound for the performance ratio of the first fit coloring on interval graphs. It is also shown that there are simple families resisting any on‐line algorithm: no on‐line algorithm can color all trees by a bounded number of colors.
On brittle graphs
Authors: Hoàng C. T. , Khouzam N. 
Published: June 2007

AbstractChvátal defined a graph G to be brittle if each induced subgraph F of G contains a vertex that is not a midpoint of any P4 or not an endpoint of any P4. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD‐free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design an O(n4) algorithm to recognize HHD‐free graphs, and also an O(n4) algorithm to construct a perfect order of an HHD‐free graph. It follows from this result that an optimal coloring and a largest clique of an HHD‐free graph can be found in O(n4) time.
Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
Authors: Jackson Bill 
Published: June 2007

AbstractWe apply proof techniques developed by L. Lovász and A. Frank to obtain several results on the arc‐connectivity of graphs and digraphs. The first results concern the operation of splitting two arcs from a vertex of an Eulerian graph or digraph in such a way as to preserve local connectivity conditions. The final result is concerned with orienting the edges of a mixed graph (consisting of vertices, undirected edges, and directed arcs) in such a way that the resulting digraph is as arc‐connected as possible.
Regular pseudo‐median graphs
Authors: Bandelt Hans‐Jürgen , Mulder Henry Martyn 
Published: June 2007

AbstractA graph is pseudo‐median if for every triple u, v, w of vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs of u, v, w, respectively (if the distance sum is odd). We show that a finite pseudo‐median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyper‐octahedron. Every self‐map of a pseudo‐median graph that preserves or collapses edges has an invariant regular pseudo‐median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo‐median graph induces a regular pseudo‐median subgraph.
A connection between a convex programming problem and the LYM property on perfect graphs
Authors: Wei Victor K. 
Published: June 2007

AbstractWe derive three equivalent conditions on a perfect graph concerning the optimal solution of a convex programming problem, the length‐width inequality, and the simultaneous vertex covering by cliques and anticliques. By combining proof techniques including Lagrangian dual, Dilworth's Theorem, and Kuhn‐Tucker Theorem, we establish a strong connection between the three topics. This provides new insights into the structure of perfect graphs. The famous Lubell‐Yamamoto‐Meschalkin (LYM) Property or Sperner Property for partially ordered sets is a specialization of our results to a subclass of perfect graphs.
Interval digraphs: An analogue of interval graphs
Authors: Das S. , Sen M. , Roy A. B. , West D. B. 
Published: June 2007

AbstractIntersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uv in the intersection digraph when the “source set” of u intersects the “terminal set” of v. Every n‐vertex digraph is an intersection digraph of ordered pairs of subsets of an n‐set, but not every digraph is an intersection digraph of convex sets in the plane. Interval digraphs are those having representations where all sets are intervals on the real line. Interval digraphs are characterized in terms of the consecutive ones property of certain matrices, in terms of the adjacency matrix and in terms of Ferrers digraphs. In particular, they are intersections of pairs of Ferrers digraphs whose union is a complete digraph.
Locally 4‐by‐4 grid graphs
Authors: Blokhuis A. , Brouwer A. E. 
Published: June 2007

AbstractWe investigate locally grid graphs. The main results are (i) a characterization of the Johnson graphs (and certain quotients of these) as locally grid graphs such that two points at distance 2 have precisely four common neighbors, and (ii) a complete determination of all graphs that are locally a 4 × 4 grid (it turns out that there are four such graphs, with 35, 40, 40, and 70 vertices).
Surface Selective Withdrawal in Sedimentation Basins
Authors: Chen I. Y. , Lai R. Y. , Karadi G. M. 
Published: June 2007

AbstractBy employing the theory of propagation of columnar disturbance, general criteria for selective withdrawal in sedimentation basins are derived. The stratified fluid is assumed to be two‐layered with different density distribution in each layer. The effects of a free surface are also included in the analysis, but the viscosity is neglected as in most other studies of stratified flow behavior. The criteria for different density profiles are established in terms of the densimetric Froude number. If the actual densimetric Froude number is smaller than its critical value, selective withdrawal will occur. Comparison of the theoretical results with the experimental data obtained by Bohan and Grace [1973] indicate an excellent agreement as long as the thickness of the bottom layer, s, is small compared to that of the top layer. Results obtained by assuming rigid upper boundary instead of free surface are also compared with the results derived in this paper. For weak stratification and small values of s they show excellent agreement. As s increases for strong stratification, the effect of free surface will become increasingly pronounced.
A General Treatise of Plane Thermoelastic Problem in Multiply‐Connected Region Exhibiting Temperature‐Dependent Properties
Authors: Sugano Y. 
Published: June 2007

AbstractThe purpose of this paper is to complete the formulation of plane thermoelastic problem in a multiply‐connected region taking into account the temperature dependencies of material properties in terms of Airy's stress function by deriving the conditions for the single valuedness of the rotation and displacements, i.e., modified Michell's conditions, and to present a method for analyzing the system of the resulting fundamental equations numerically by the use of finite difference method.
Analytische Mechanik der beschränkten Konfigurationsräume
Authors: Baumgarte J. 
Published: June 2007

AbstractVon besonderem Interesse sind in der Mechanik Bindungen, die eine Begrenzung des Konfigurationsraumes erzwingen. Solche Bindungen werden realisiert durch starre, evtl. masselose Stangen, reibungsfreie Gelenke und insbesondere durch masselose dehnstarre Seile. In dieser Arbeit werden parametrisierte holonome Bindungen eingeführt, die eine allgemeine Beschreibung von Konfigurationsraumbeschränkungen ermöglichen. Über ein Variationsproblem werden die Formeln für Geschwindigkeitssprünge an den Grenzen des Konfigurationsraumes explizit angegeben. In diesen Formeln lassen sich sowohl dissipative Anteile (nichtelastische Vorgänge) als sogar auch Verletzungen der klassischen holonomen Bindungen — wie z. B. Zerstörung von Gelenkverbindungen — explizit angeben.
Konservative Differenzenmethoden zur Modellierung eindimensionaler Diffusionsprozesse mit Unstetigkeiten an einer Phasengrenze
Authors: Friedrich V. , Windisch G. 
Published: June 2007

AbstractIn einem Zweiphasensystem mit bekannter Phasengrenze wird ein eindimensionaler Diffusionsprozeß betrachtet, wobei Bedingungen für die Konservativität an der Phasengrenze, an der Unstetigkeiten auftreten, abgeleitet werden. Mit der Integro‐Interpolationsmethode wird eine Klasse konservativer Differenzenschemata erzeugt. für Spezialfälle werden Bedingungen für die eindeutige Lösbarkeit abgeleitet und Untersuchungen zur Stabilität durchgeführt.
Stabilitätsgebiete expliziter linearer Zweischrittverfahren
Authors: Bachmann K. H. 
Published: June 2007

AbstractDie Stabilitätsgebiete konsistenter expliziter linearer Zweischrittverfahren werden auf ihre Ausdehnung längs der negativ reellen Achse untersucht. Diese Ausdehnung wird in Abhängigkeit von zwei Parametern dargestellt und kann durch geeignete Parameterwahl beliebig groß gemacht werden. Daher sind Verfahren konstruierbar, die fast A (0)‐stabil sind.
Newton‐Type Decomposition Methods for Equations Arising in Network Analysis
Authors: Hoyer W. , Schmidt J. W. 
Published: June 2007

AbstractThis paper presents two‐ and multilevel Newton‐type decomposition methods for the iterative solution of large nonlinear systems of equations which arise with a special block‐wise sparsity pattern e.g. in electric circuit analysis. The structure of the systems is widely utilized by the proposed algorithms, which only require soling linear subsystems of the sizes of the diagonal blocks. The methods developed are shown to be locally superlinearly convergent.
Eine Klasse asymptotisch stabiler autonomer Systeme und Normschranken für spezielle Reaktions‐Diffusions‐Prozesse
Authors: Rautmann R. 
Published: June 2007

AbstractDurch zwei Annahmen über den Vorzeichenverlauf der beiden Komponenten des Richtungsfeldes wird eine Klasse ebener autonomer Systeme definiert. Die Anfangswertaufgabe dieser Systeme ist global eindeutig lösbar, alle Lösungen sind (asymptotisch) stabil, und es gibt eine global attraktive stationäre Lösung. Für klassische Lösungen spezieller nichtlinearer Reaktions‐Diffusions‐Gleichungssysteme in beschränkten n‐dimensionalen Gebieten ergeben sich so globale asymptotisch stabile Normschranken sowie eine Übersicht über das mögliche Wachstumsverhalten der Lösungen in Abhängigkeit von Normschranken der Anfangswerte.
Hemivariational Inequalities and Substationarity in the Static Theory of v. Kármán Plates
Authors: Panagiotopoulos P. D. 
Published: June 2007

AbstractThe present paper deals with nonconvex BVPs in the framework of v. Kármán plate theory which lead to hemivariational inequalities and substationarity problems. By means of the method of regularization and with the aid of compactness arguments the existence of the solution for coercive and semicoercive problems is proved. Certain approximation results are given, too.
Ein gemischtes und in sich duales Variationsprinzip für beliebig gekrümmte Schalen
Authors: Zuercher J.‐P. , Schumann W. 
Published: June 2007

AbstractDie vorliegende Arbeit befaßt sich mit einem gemischten, in sich vollständig dualen Variationsprinzip der Schalentheorie. Zwei Skalare und zwei Vektoren bilden die unabhängigen Variablen und führen zu paarweise dualen Differentialausdrücken im Innern und am Rand.
Zur Konvergenz und Stabilität von direkten Mehrschritt‐Verfahren für die spezielle Differentialgleichung y(m) = f(x, y)
Authors: Filippi S. , Röhr H. 
Published: June 2007

AbstractIn dieser Arbeit werden die wichtigsten Konvergenz‐ und Stabilitätssätze von Henrici für y″ = f(x, y) sowohl für die direkten klassischen als auch für die direkten verallgemeinerten Mehrschritt‐ Verfahren auf y(m) = f(x, y), m > 2, erweitert. Ferner wird erstmals für die direkten klassischen und verallgemeinerten Mehrschritt‐ Verfahren eine von der Ordnung m abhängige Stabilitäts‐Barriere aufgestellt.
Allgemeine Variationsprinzipien in den Evolutionsaufgaben der Kontinuumsmechanik und der diskreten Mechanischen Systeme
Authors: Rosenberg J. 
Published: June 2007

AbstractIn der Arbeit wird eine allgemeine Methode zur Formulierung von Variationsprinzipien für Evolutionsrandwertprobleme vorgestellt. Diese Methode geht aus der Wahl der Bilinearform als inneres Produkt hervor. Neben der klassischen Bilinearform wird auch die konvolutorische Form verwendet, deren Einsatz es erlaubt, Variationsprinzipien zu formulieren, die auch die Anfangsbedingungen enthalten. Die dargelegte Methode wird auf die isotherme Strömung viskoser Flüssigkeiten und auf die Mechanik diskreter mechanischer Systeme angewendet.
Bemerkungen zum d'Alembertschen Prinzip
Authors: Baumgarte J. , Ostermeyer G. P. 
Published: June 2007

AbstractBei der Berücksichtigung von Bindungen in mechanischen Systemen liefert das d'Alembertsche Prinzip zwei bekannte Vorgehensweisen: Die Reduktion der Ordnung des Differentialgleichungssystems, oder: Einführung von Zwangskräften. Der erste Weg führt auf die Einführung generalisierter Variabler, die den Bindungen exakt genügen. Aber diese Variablen sind nicht immer einfach zu finden. Der zweite Weg liefert einfach aufzustellende Differentialgleichungen, führt aber zu zusätzlichen Instabilitäten in den Gleichungen, so daß die numerische Lösung die Bindungsgleichungen mit der Zeit erheblich verletzt.Diese Arbeit beschreibt einen dritten Weg, die Einführung quasi‐generalisierter Variabler. Die resultierenden Bewegungsgleichungen sind einfach aufzustellen (keine Reduktion der Ordnung des Systems!) und ihre numerische Lösung genügt den Bindungsgleichungen exakt (keine Zwangkräfte).
Zur Identifikation mehrfach monotoner Funktionen
Authors: Berg L. 
Published: June 2007

AbstractBehandelt wird das Ausgleichsproblem für gegebene Näherungswerte einer mehrfach monotonen Funktion. Im allgemeinen Fall werden die Lösungen durch Minimalpolynome eingeschlossen. Im sogenannten Idealfall gibt es ein eindeutig bestimmtes Ausgleichspolynom, dessen Grad in optimaler Weise festgelegt ist. Zur Berechnung dieses Polynoms wird eine Verfahren mit verhältnismäßig geringem Speicherplatzbedarf angegeben.
On Approximate Computation of the Values of the Normal Derivative of Solutions to Linear Partial Differential Equations of Second Order with Application to Abel's Integral Equation
Authors: Gerlach W. , Wolfersdorf L. V. 
Published: June 2007

AbstractFor the numerical computation of the normal derivative of solutions to linear partial differential equations of second order from the boundary values of the solutions an operator method of regularization with unbounded accretive operator is proposed. The method is applied to the numerical solution of Abel's integral equation.
Efficient Numerical Integration on the Surface of a Sphere
Authors: Bažant P. , Oh B. H. 
Published: June 2007

AbstractSeveral new numerical integration formulas on the surface of a sphere in three dimensions are derived. These formulas are superior to the existing ones in that for the same degree of approximation they require fewer integration points for functions with central or planar symmetry. Furthermore, a general method of deriving the integration formulas, which achieves conceptual simplicity at the expense of extensive numerical work left for a computer, is demonstrated. In this method, the coefficients of the integration formula are determined from a system of linear algebraic equations directly representing the conditions for a certain number of terms of the three‐dimensional Taylor series expansion of the integrated function about the center of the sphere to vanish, while the unknown locations of the integration points are determined from a condition for the next term (or terms) of the expansion to vanish, and if it cannot be made to vanish, then from a condition for minimizing the magnitude of this term (or these terms). Finally, we formulate a new condition of optimality of the integration formulas which is important for the integration error in certain applications.
Weakly Singular Discrete Gronwall Inequalities
Authors: Dixon J. , McKee S. 
Published: June 2007

AbstractGeneralizations of the classical Gronwall inequality when the kernel of the associated integral equation is weakly singular are presented. The continuous and discrete versions are both given; the former is included since it suggests the latter by analogy. This work is motivated by convergence studies of discretization methods for Volterra integral and integro‐differential equations. The results are all given in a form designed to be of most use to numerical analysts.
Absence of population substructuring in Zimbabwe chicken ecotypes inferred using microsatellite analysis
Authors: Muchadeyi F. C. , Eding H. , Wollny C. B. A. , Groeneveld E. , Makuza S. M. , Shamseldin R. , Simianer H. , Weigend S. 
Published: June 2007

SummaryThe objective of this study was to investigate the population structure of village chickens found in the five agro‐ecological zones of Zimbabwe. Twenty‐nine microsatellites were genotyped for chickens randomly selected from 13 populations, including the five eco‐zones of Zimbabwe (n = 238), Malawi (n = 60), Sudan (n = 48) and six purebred lines (n = 180). A total of 280 alleles were observed in the 13 populations. Forty‐eight of these alleles were unique to the Zimbabwe chicken ecotypes. The average number (±SD) of alleles/locus was 9.7 ± 5.10. The overall heterozygote deficiency in the Zimbabwe chickens (FIT ± SE) was 0.08 ± 0.01, over 90% of which was due to within‐ecotype deficit (FIS). Small Nei's standard genetic distances ranging from 0.02 to 0.05 were observed between Zimbabwe ecotypes compared with an average of 0.6 between purebred lines. The structure software program was used to cluster individuals to 2 ≤ K ≤ 7 assumed clusters. The most probable clustering was found at K = 6. Ninety‐seven of 100 structure runs were identical, in which Malawi, Sudan and purebred lines split out as independent clusters and the five Zimbabwe ecotypes clustered into one population. The within‐ecotype marker‐estimated kinships (mean = 0.13) differed only slightly from the between‐ecotype estimates. Results from this study lead to a rejection of the hypothesis that village chickens are substructured across agro‐ecological zones but indicated high genetic diversity within the Zimbabwe chicken population.
A 12 000‐rad whole‐genome radiation hybrid panel in sheep: application to the study of the ovine chromosome 18 region containing a QTL for scrapie susceptibility
Authors: Laurent P. , Schibler L. , Vaiman A. , Laubier J. , Delcros C. , Cosseddu G. , Vaiman D. , Cribiu E. P. , Yerle M. 
Published: June 2007

SummaryWhole‐genome radiation hybrid (RH) panels have been constructed for several species, including cattle. RH panels have proven to be an extremely powerful tool to construct high‐density maps, which is an essential step in the identification of genes controlling important traits, and they can be used to establish high‐resolution comparative maps. Although bovine RH panels can be used with ovine markers to construct sheep RH maps based on bovine genome organization, only some (c. 50%) of the markers available in sheep can be successfully mapped in the bovine genome. So, with the development of genomics and genome sequencing projects, there is a need for a high‐resolution RH panel in sheep to map ovine markers. Consequently, we have constructed a 12 000‐rad ovine whole‐genome RH panel. Two hundred and eight hybrid clones were produced, of which 90 were selected based on their retention frequency. The final panel had an average marker retention frequency of 31.8%. The resolution of this 12 000‐rad panel (SheepRH) was estimated by constructing an RH framework map for a 23‐Mb region of sheep chromosome 18 (OAR18) that contains a QTL for scrapie susceptibility.
Identification of 10 882 porcine microsatellite sequences and virtual mapping of 4528 of these sequences
Authors: Karlskov‐Mortensen P. , Hu Z. L. , Gorodkin J. , Reecy J. M. , Fredholm M. 
Published: June 2007

SummaryA total of 10 882 porcine microsatellite repeats were identified in genomic shotgun sequences from the Sino‐Danish Pig Genome Sequencing Consortium (http://www.piggenome.dk). Of these, 4528 microsatellites were placed on a pig–human comparative map by blast analysis of porcine sequences against the human genome (blast cut‐off threshold =1 × 10−5). All microsatellite sequences placed on the comparative map are accessible at http://www.animalgenome.org/QTLdb/pig.html. These sequences increase the number of identified microsatellites in the porcine genome by several orders of magnitude. They are a new resource of microsatellite sequences for generating markers to be used in linkage studies and in fine mapping and positional cloning of quantitative trait loci.