  An error occurred while sending the email. Please try again.

Proceed reservation?

Export
• 1 Electronic Resource
Springer
Graphs and combinatorics 15 (1999), S. 257-265
ISSN: 1435-5914
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract.  Given a graph G, we define its partially square graph G * as the graph obtained by adding edges uv whenever the vertices u and v have a common neighbor x satisfying the condition N G[x]⊆N G[u]∪N G [v], where N G[x]=N G(x)∪{x}. In particular, this condition is satisfied if x does not center a claw (an induced K 1,3). Obviously G⊆G *⊆G 2, where G 2 is the square of G. We prove that a k-connected graph (k≥2) G is hamiltonian if the independence number α(G *) of G * does not exceed k. If we replace G * by G we get a well known result of Chvátal and Erdoës. If G is claw-free and G * is replaced by G 2 then we obtain a result of Ainouche, Broersma and Veldman. Relationships between connectivity of G and independence number of G * for other hamiltonian properties are also given in this paper.
Type of Medium: Electronic Resource
Signatur Availability
• 2 Electronic Resource
Springer
Combinatorica 20 (2000), S. 219-226
ISSN: 1439-6912
Keywords: AMS Subject Classification (1991) Classes:  05C38, 05C70, 05C35
Source: Springer Online Journal Archives 1860-2000
Topics: Mathematics
Notes: G =(V,E) is a 2-connected graph, and X is a set of vertices of G such that for every pair x,x' in X, , and the minimum degree of the induced graph 〈X〉 is at least 3, then X is covered by one cycle. This result will be in fact generalised by considering tuples instead of pairs of vertices. Let be the minimum degree in the induced graph 〈X〉. For any , . If , and , then X is covered by at most (p-1) cycles of G. If furthermore , (p-1) cycles are sufficient. So we deduce the following: Let p and t ( ) be two integers. Let G be a 2-connected graph of order n, of minimum degree at least t. If , and , then V is covered by at most cycles, where k is the connectivity of G. If furthermore , (p-1) cycles are sufficient. In particular, if and , then G is hamiltonian.
Type of Medium: Electronic Resource
Signatur Availability
• 3 Electronic Resource
Springer
Combinatorica 16 (1996), S. 407-412
ISSN: 1439-6912
Keywords: 05 C 38 ; 05 C 70
Source: Springer Online Journal Archives 1860-2000
Topics: Mathematics
Notes: Abstract We show that if $$\sum\limits_{x \in S} {\deg _{G^x } \geqslant \left| G \right|}$$ , for every stable set $$S \subseteq V\left( G \right),\left| S \right| = k$$ , then the vertex set ofG can be covered withk−1 cycles, edges or vertices. This settles a conjecture by Enomoto, Kaneko and Tuza.
Type of Medium: Electronic Resource
Signatur Availability
Close ⊗