bluuebunny/crossref_metadata_2025_split huggingface dataset:
Star chromatic numbers and products of graphs
Authors: Zhu Xuding 
Published: June 2007

AbstractThe star‐chromatic number of a graph, a concept introduced by Vince, is natural generalization of the chromatic number of a graph. We point out an alternate definition of the star‐chromatic number, which sheds new light on the relation of the star‐chromatic number and the ordinary chromatic number. This new point of view allows us to answer several problems posed by Vince. We then study the starchromatic number from the perspective of graph homomorphisms and of graph products.
Edge‐disjoint paths and cycles in n‐edge‐connected graphs
Authors: Huck Andreas 
Published: June 2007

AbstractWe consider finite undirected loopless graphs G in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal n ≥ 0 with the following property: If G is an n‐edge‐connected graph, s1, ⃛,sk, t1, ⃛,tk are vertices of G, and f1, ⃛,fl, g1, ⃛,gl, are pairwise distinct edges of G, then for each i = 1, ⃛, k there exists a path Pi in G, connecting si and ti and for each i = 1, ⃛,l there exists a cycle Ci in G containing fi and gi such that P1, ⃛,Pk, C1, ⃛, Cl are pairwise edge‐disjoint. We give upper and lower bounds for g(k, l).
The connectivity of large digraphs and graphs
Authors: Fiol M. A. 
Published: June 2007

AbstractThis paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter lpi;, 0 ≤ π ≤ δ − 2, related with the number of short paths (in the case of graphs l0 = ⌊(g − 1)/2⌋ where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ 2 + … + ΔD (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc‐connectivity of G,
equation image
.Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.
Perfect k‐line graphs and k‐total graphs
Authors: Lê Van Bang 
Published: June 2007

AbstractThe concept of the line graph can be generalized as follows. The k‐line graph Lk(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in Lk(G) if and only if they have in G k − 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3‐line graphs and 3‐total graphs. Moreover, perfect 3‐line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley & Sons, Inc.
On sparse subgraphs preserving connectivity properties
Authors: Frank András , Ibaraki Toshihide , Nagamochi Hiroshi 
Published: June 2007

AbstractFrom a theorem of W. Mader [“Über minimal n‐fach zusammenhängende unendliche Graphen und ein Extremal problem,” Arch. Mat., Vol. 23 (1972), pp. 553–560] it follows that a k‐connected (k‐edge‐connected) graph G = (V,E) always contains a k‐connected (k‐edge‐connected) subgraph G′ = (V,E′) with O(k|V|) edges. T. Nishizeki and S. Poljak “K‐Connectivity and Decomposition of Graphs into Forests,” Discrete Applied Mathematics, submitted) showed how G′ can be constructed as the union of k forests. H. Nagamochi and T. Ibaraki [A Linear Time Algorithm for Finding a Sparse k‐Connected Spanning Subgraph of a k‐Connected Graph, Algorithmica, Vol. 7 (1992), pp. 583–596] constructed such a subgraph Gk in linear time and showed for any pair x,y of nodes that Gk contains k openly disjoint (edge‐disjoint) paths connecting x and y if G contains k openly disjoint (edge‐disjoint) paths connecting x and y (even if G is not k‐connected (k‐edge‐connected)). In this article we provide a much shorter proof of a common generalization of the edge‐ and node‐connectivity versions showing that the subgraph Gk has a certain mixed connectivity property. © 1993 John Wiley & Sons, Inc.
Maximal independent sets in bipartite graphs
Authors: Liu Jiuqiang 
Published: June 2007

AbstractA maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order n and the extremal graphs as well as the corresponding results for connected bipartite graphs. © 1993 John Wiley & Sons, Inc.
Independence and graph homomorphisms graph homomorphisms
Authors: Albertson Michael O. , Chan Lily , Haas Ruth 
Published: June 2007

AbstractA graph with n vertices that contains no triangle and no 5‐cycle and minimum degree exceeding n/4 contains an independent set with at least (3n)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7‐cycle and invoking the No Homomorphism Lemma. For k ≥ 4, a graph with n vertices, odd girth 2k+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2k+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.
Contractions to k8
Authors: Jørgensen Leif K. 
Published: June 2007

AbstractIt is proved that the maximal number of edges in a graph with n ≧ 8 vertices that is not contractible to K8 is 6n − 21, unless 5 divides n, and the only graphs with n = 5m vertices and more than 6n − 21 edges that are not contractible to K8 are the K5(2)‐cockades that have exactly 6n − 20 edges.
Almost claw‐free graphs
Authors: Ryjáček Zdeněk 
Published: June 2007

AbstractWe say that G is almost claw‐free if the vertices that are centers of induced claws (K1,3) in G are independent and their neighborhoods are 2‐dominated. Clearly, every claw‐free graph is almost claw‐free. It is shown that (i) every even connected almost claw‐free graph has a perfect matching and (ii) every nontrivial locally connected K1,4‐free almost claw‐free graph is fully cycle extendable.
Which generalized petersen graphs are cayley graphs?
Authors: Nedela Roman , Škoviera Martin 
Published: June 2007

AbstractThe generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex‐set {uj; i ϵ Zn} ∪ {vj; i ϵ Zn}, and edge‐set {uiui, uivi, vivi+k, iϵZn}. In the paper we prove that(i) GP(n, k) is a Cayley graph if and only if k2  1 (mod n); and(ii) GP(n, k) is a vertex‐transitive graph that is not a Cayley graph if and only if k2  ‐1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1‐skeleton of the dodecahedon.The proof of (i) is based on the classification of orientable regular embeddings of the n‐dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211‐218]. © 1995 John Wiley & Sons, Inc.
On the maximum number of edges in a c4‐free subgraph of qn
Authors: Brass Peter , Harborth Heiko , Nienborg Hauke 
Published: June 2007

AbstractFor the maximum number f(n) of edges in a C4‐free subgraph of the n‐dimensional cube‐graph Qn we prove f(n) ≥ 1/2(n +√n)2n−1 for n = 4r, and f(n) ≥ 1/2(n +0.9√n)2n−1 for all n ≥ 9. This disproves one version of a conjecture of P. Erdos. © 1995 John Wiley & Sons, Inc.
Retract‐collapsible graphs and invariant subgraph properties
Authors: Polat Norbert 
Published: June 2007

AbstractA (finite or infinite) graph G is retract‐collapsible if it can be dismantled by deleting systematically at each step every vertex that is strictly dominated, in such a way that the remaining subgraph is a retract of G, and so as to get a simplex at the end. A graph is subretract‐collapsible if some graph obtained by planting some rayless tree at each of its vertices is retract‐collapsible. It is shown that the subretract‐colapsible graphs are cop‐win; and that a ball‐Helly graph is subretract‐collapsible if and only if it has no isometric infinite paths (thus in particular if it has no infinite paths, or if it is bounded). Several fixed subgraph properties are proved. In particular, if G is a subretract‐collapsible graph, and f a contraction from G into G, then (i) if G has no infinite simplices, then f(S) = S for some simplex S of G; and (ii) if the dismantling of G can be achieved in a finite number of steps and if some family of simplices of G has a compacity property, then there is a simplex S of G such that f(S) ⊆ S. This last result generalizes a property of bounded ball‐Helly graphs. © 1995 John Wiley & Sons, Inc.
Factorization of regular multigraphs into regular graphs
Authors: El‐Zanati S. I. , Plantholt M. J. , Tipnis S. K. 
Published: June 2007

AbstractA regular multigraph with maximum multiplicity r and degree rs cannot always be factored into r s‐regular simple graphs. It is shown, however, that under general conditions a similar factorization can be achieved if we first allow the addition or deletion of a relatively small number of hamilton cycles. Based on this result, we give extensions of some known factorization results on simple graphs to new results on multigraphs. © 1995 John Wiley & Sons, Inc.
Generalized steinhaus graphs
Authors: Brand Neal , Morton Margaret 
Published: June 2007

AbstractA generalized Steinhaus graph of order n and type s is a graph with n vertices whose adjacency matrix (ai,j) satisfies the relation magnified image where 2 ≦i≦n−1, i + s(i − 1 ≦ j ≦ n, cr,i,j ϵ {0,1} for all 0 ≦ r ≦ s(i) −1 and cs(i)−1,i,j = 1. The values of s(i) and cr,i,j are fixed but arbitrary. Generalized Steinhaus graphs in which each edge has probability ½ are considered. In an article by A. Blass and F. Harary [“Properties of Almost All Graphs and Complexes,” Journal of Graph Theory, Vol. 3 (1976), pp. 225–240], a collection of first‐order axioms are given from which any first‐order property in graph theory or its negation can be deduced. We show that almost all generalized Steinhaus graphs satisfy these axioms. Thus the first‐order theory of random generalized Steinhaus graphs is identical with the theory of random graphs. Quasi‐random properties of graphs are described by F. R. K. Chung, R. L. Graham, and R. M. Wilson, [“Quasi‐Random Graphs,” Combinatorica, Vol. 9 (1989), pp. 345–362]. We conclude by demonstrating that almost all generalized Steinhaus graphs obey Property 2 and hence all equivalent quasi‐random properties. © 1996 John Wiley & Sons, Inc.
Asymptotic enumeration of full graphs
Authors: Kleitman D. J. , Lasaga F. R. , Cowen L. J. 
Published: June 2007

AbstractA full graph on n vertices, as defined by Fulkerson, is a representation of the intersection and containment relations among a system of n sets. It has an undirected edge between vertices representing intersecting sets, and a directed edge from a to b if the corresponding set A contaisn B. We give a unified argument to show that asymptotically, almost all full graphs can be obtained by taking an arbitrary undirected graph in the n vertices, distinguishing a clique in this graph that need not be maximal, and then adding directed edges going out from each vertex in the clique to all vertices to which there is not already an existing undirected edge. © 1996 John Wiley & Sons, Inc.
A circular‐arc characterization of certain rectilinear drawings
Authors: Stueckle S. K. , Piazza B. L. , Ringeisen R. D. 
Published: June 2007

AbstractIn this paper we give a construction that produces exactly those graphs having maximum rectilinear crossing number equal to the subthrackle bound. We then prove a theorem characterizing these graphs in terms of proper circular‐arc graphs. © 1996 John Wiley & Sons, Inc.
From steiner centers to steiner medians
Authors: Oellermann Ortrud R. 
Published: June 2007

AbstractThe Steiner distance of set S of vertices in a connected graph G is the minimum number of edges in a connected subgraph of G containing S. For n ≥ 2, the Steiner n‐eccentricity en(v) of a vertex v of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contain v. The Steiner n‐center of G is the subgraph induced by those vertices of G having minimum n‐eccentricity. The Steiner n‐distance of a vertex v of G is defined as magnified image. The Steiner n‐median of G is the subgraph of G induced by the vertices of G of minimum Steiner n‐distance. Known algorithms for finding the Steiner n‐centers and Steiner n‐medians of trees are used to show that the distance between the Steiner n‐centre and Steiner n‐median of a tree can be arbitrarily large. Centrality measures that allow every vertex on a shortest path from the Steiner n‐center to the Steiner n‐median of a tree to belong to the “center” with respect to one of these measures are introduced and several proeprties of these centrality measures are established. © 1995 John Wiley & Sons, Inc.
Degree‐bounded coloring of graphs: Variations on a theme by brooks
Authors: Hakimi S. L. , Mitchem J. , Schmeichel E. F. 
Published: June 2007

AbstractA graph G is degree‐bounded‐colorable (briefly, db‐colorable) if it can be properly vertex‐colored with colors 1,2, …, k ≤ Δ(G) such that each vertex v is assigned a color c(v) ≤ v. We first prove that if a connected graph G has a block which is neither a complete graph nor an odd cycle, then G is db‐colorable. One may think of this as an improvement of Brooks' theorem in which the global bound Δ(G) on the number of colors is replaced by the local bound deg v on the color at vertex v. Extending the above result, we provide an algorithmic characterization of db‐colorable graphs, as well as a nonalgorithmic characterization of db‐colorable trees. We briefly examine the problem of determining the smallest integer k such that G is db‐colorable with colors 1, 2,…, k. Finally, we extend these results to set coloring. © 1995, John Wiley & Sons, Inc.
An induced subgraph characterization of domination perfect graphs
Authors: Zvervich Igor E. , Zverovich Vadim E. 
Published: June 2007

AbstractLet γ(G) ι(G) be the domination number and independent domination number of a graph (G), respectively. A graph (G) is called domination perfect if γ(H) = ι(H), for every induced subgraph H of (G). There are many results giving a partial characterization of domination perfect graphs. In this paper, we present a finite induced subgraph characterization of the entire class of domination perfect graphs. The list of forbidden subgraphs in the charcterization consists of 17 minimal domination imperfect graphs. Moreover, the dominating set and independent dominating set problems are shown to be both NP‐complete on some classes of graphs. © 1995 John Wiley & Sons, Inc.
Hamiltonicity for K1, r‐free graphs
Authors: Chen Guantao , Schelp R. H. 
Published: June 2007

AbstractIn this paper, we investigate the Hamiltonicity of K1,r‐free graphs with some degree conditions. In particular, let G be a k‐connected grph of order n≧3 which is K1,4‐free. If magnified image for every independent set {v0, v1, …, vk} then G is hamiltonian. We use an upper bound for the independence number of K1,r‐free graphs to extent the above result to K1,r‐free graphs. Hamiltonian connected and, more generally, q‐edge hamiltonian properties are studied here as well. © 1995 John Wiley & Sons, Inc.
Hamiltonian cycles in 2‐connected claw‐free‐graphs
Authors: Li Hao 
Published: June 2007

AbstractM. Matthews and D. Sumner have proved that of G is a 2‐connected claw‐free graph of order n such that δ ≧ (n − 2)/3, then G is hamiltonian. We prove that the bound for the minimum degree δ can be reduced to n/4 under the additional condition that G is not in F, where F is the set of all graphs defined as follows: any graph H in F can be decomposed into three vertex disjoint subgraphs H1, H2, H3 such that magnified image, where ui, vi ϵ V(Hi), uj vj ϵ V(Hj) 1 ϵ i ≦ j ≦ 3. Examples are given to show that the bound n/4 is sharp. © 1995 John Wiley & Sons, Inc.
Cycles through particular subgraphs of claw‐free graphs
Authors: Broersma H. J. , Lu M. 
Published: June 2007

AbstractLet G be a 2‐connected claw‐free graph on n vertices, and let H be a subgraph of G. We prove that G has a cycle containing all vertices of H whenever α3(H) ≧ κ(G), where α3(H) denotes the maximum number of vertices of H that are pairwise at distance at least three in G, and κ(G) denotes the connectivity of G. This result is an analog of a result from the thesis of Fournier, and generalizes the result of Zhang that G is hamiltonian if the degree sum of any κ(G) + 1 pairwise nonadjacent vertices is at least n − κ(G). © 1995 John Wiley & Sons, Inc.
Are disc pressure, stress, and osmolarity affected by intra‐ and extrafibrillar fluid exchange?
Authors: Schroeder Yvonne , Sivan Sarit , Wilson Wouter , Merkher Yulia , Huyghe Jacques M. , Maroudas Alice , Baaijens Frank P.T. 
Published: June 2007

AbstractBecause extrafibrillar water content dictates extrafibrillar osmolarity, we aimed to determine the influence of intra‐ and extrafibrillar fluid exchange on intradiscal pressures and stresses. As experimental results showed that extrafibrillar osmolarity affects intervertebral disc cell gene expression and crack propagation, quantification of the effects of changes in intra‐ and extrafibrillar fluid exchange is physiologically relevant. Therefore, our 3D osmoviscoelastic finite element (FE) model of the intervertebral disc was extended to include the intra‐ and extrafibrillar water differentiation. Two simulations were performed, one without intrafibrillar fluid and one with intrafibrillar fluid fraction as a function of the extrafibrillar osmotic pressure. The intrafibrillar fluid fraction as a function of the extrafibrillar osmotic pressure was exponentially fitted to human data and implemented into the model. Because of the low collagen content in the nucleus, no noticeable differences in intradiscal pressure estimation were observed. However, values of extrafibrillar osmolarity, hydrostatic pressure, and the total tissue stress calculated for the annulus were clearly different. Stresses, hydrostatic pressure, and osmolarity were underestimated when the intrafibrillar water value was neglected. As the loading increased, the discrepancies increased. In conclusion, the distribution of pressure and osmolarity in the disc is affected by intra‐ and extrafibrillar water exchange. © 2007 Orthopaedic Research Society. Published by Wiley Periodicals, Inc. J Orthop Res 25:1317–1324, 2007
Postoperative serum attenuates LPS‐induced release of TNF‐α in orthopaedic surgery
Authors: Reikerås Olav , Sun Jingbo , Wang Jacob E. , Aasen Ansgar O. 
Published: June 2007

AbstractStudies with ex vivo stimulation of whole blood samples from injured patients have revealed a diminished production capacity for a broad range of secretory products, including inflammatory cytokines. Recent interest has focused on the release of mediators in serum that depress the cell‐mediated immune response following trauma. The involvement of the lipid mediator prostaglandin E2 (PGE2) has been assumed because it is a potent endogenous immunosuppressor. In the present study, we tested the hypothesis that inhibitory substances circulating in the patient's serum after a major musculoskeletal trauma might impair leukocyte function by evaluating the effect of such serum on cytokine release in a whole blood model. Six females and three males undergoing elective total hip replacement were included in the study. Ex vivo LPS‐induced TNF‐α and IL‐10 were measured in whole blood sampled preoperatively and added serum taken before, at the end of operation, and at postoperative days 1 and 6 with saline as negative control. LPS induced significant releases of TNF‐α and IL‐10 in whole blood. Addition of preoperative, postoperative, and day‐1 postoperative serum did not alter the LPS‐induced release of TNF‐α as compared to saline. In the presence of serum from postoperative day 6, however, the expression of TNF‐α was significantly reduced as compared to saline and preoperative serum (p = 0.021 and 0.008, respectively). Neither of the serum samples altered the release of IL‐10. PGE2 was significantly (p = 0.008) increased in serum at postoperative day 6 as compared to preoperative levels. In conclusion, these data show that at day 6 after major orthopaedic surgery, the patient serum contained activity that inhibited ex vivo LPS‐induced TNF‐α release. The potent TNF‐α inhibitory activity found at day 6 after injury correlated with increased levels of PGE2 and indicates cell‐mediated hyporesponsiveness to a second stimulus. © 2007 Orthopaedic Research Society. Published by Wiley Periodicals, Inc. J Orthop Res 25:1395–1400, 2007
Nonpharmacological treatment, fludrocortisone, and domperidone for orthostatic hypotension in Parkinson's disease
Authors: Schoffer Kerrie L. , Henderson Robert D. , O'Maley Karen , O'Sullivan John D. 
Published: June 2007

AbstractThere is limited evidence for the treatment of orthostatic hypotension in idiopathic Parkinson's disease. The objective of this study was to determine the efficacy of three treatments (nonpharmacological therapy, fludrocortisone, and domperidone). Phase I assessed the compliance, safety, and efficacy of nonpharmacological measures. Phase II was a double‐blind randomized controlled crossover trial of the two medications. Primary outcome measures consisted of the orthostatic domain of the Composite Autonomic Symptom Scale (COMPASS‐OD), a clinical global impression of change (CGI), and postural blood pressure testing via bedside sphygmomanometry (Phase I) or tilt table testing (Phase II). For the 17 patients studied, nonpharmacological therapy did not significantly alter any outcome measure. Both medications improved the CGI and COMPASS‐OD scores. There was a trend towards reduced blood pressure drop on tilt table testing, with domperidone having a greater effect. © 2007 Movement Disorder Society
Clinical correlates of mitochondrial function in Huntington's disease muscle
Authors: Turner Christopher , Cooper J. Mark , Schapira Anthony H. V. 
Published: June 2007

AbstractHuntington's disease (HD) is caused by an abnormally expanded CAG repeat in the IT‐15 gene, which encodes a widely expressed protein called huntingtin. Abnormalities of mitochondrial respiratory chain function, specifically complex II/III, have been identified in HD striatum and defects of energy metabolism have been demonstrated in vivo in skeletal muscle in both symptomatic and presymptomatic HD patients. We have investigated respiratory chain function using histochemical and biochemical methods in HD skeletal muscle from 12 patients and compared these with 12 age and sex‐matched controls. The data from the HD patients were related to clinical parameters of HD including the Unified Huntington's Disease Rating Scale (UHDRS). There were positive correlations between CAG repeat years (a product of CAG repeat length and age) and both motor (P < 0.002) and cognitive (P < 0.01) scores of the UHDRS. There was no significant difference in the activities of complexes I to IV compared to age‐matched controls. However, there were significant correlations for individual HD complex II/III activities with disease duration (P = 0.017), repeat years (P = 0.032), and cognitive scores (P = 0.019). There was also evidence from ultrastructural studies that inclusion formation may occur in HD muscle. These results provide additional evidence that mutant huntingtin influences mitochondrial complex II/III function in non‐neuronal tissue (skeletal muscle) and suggest that muscle may be a potential marker of disease progression in HD. © 2007 Movement Disorder Society