Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
  • 1
    Electronic Resource
    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
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    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
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    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
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...