All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 8 Next

Displaying 141 – 160 of 374

Showing per page

Perfect connected-dominant graphs

Igor Edmundovich Zverovich (2003)

Discussiones Mathematicae Graph Theory

If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number γ c ( G ) of G. A graph G is called a perfect connected-dominant graph if γ ( H ) = γ c ( H ) for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.

Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases

E. Bampis, A. Giannakos, A. Karzanov, Y. Manoussakis, I. Milis (2010)

RAIRO - Theoretical Informatics and Applications

It is known that finding a perfect matching in a general graph is AC0-equivalent to finding a perfect matching in a 3-regular (i.e. cubic) graph. In this paper we extend this result to both, planar and bipartite cases. In particular we prove that the construction problem for perfect matchings in planar graphs is as difficult as in the case of planar cubic graphs like it is known to be the case for the famous Map Four-Coloring problem. Moreover we prove that the existence and construction...

Perfect Set of Euler Tours of Kp,p,p

T. Govindan, A. Muthusamy (2016)

Discussiones Mathematicae Graph Theory

Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G, is Hamilton cycle decomposable. In this paper, we construct a perfect set of Euler tours for the complete tripartite graph Kp,p,p for any prime p and hence prove Bermond’s conjecture for G = Kp,p,p.

Currently displaying 141 – 160 of 374