NP-completeness of the planar separator problems.
Fukuyama, Junichiro (2006)
Journal of Graph Algorithms and Applications
Similarity:
Fukuyama, Junichiro (2006)
Journal of Graph Algorithms and Applications
Similarity:
Przybylo, Jakub (2008)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
J. Adrian Bondy, Hajo J. Broersma, Jan van den Heuvel, Henk Jan Veldman (2002)
Discussiones Mathematicae Graph Theory
Similarity:
An (edge-)weighted graph is a graph in which each edge e is assigned a nonnegative real number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges, and an optimal cycle is one of maximum weight. The weighted degree w(v) of a vertex v is the sum of the weights of the edges incident with v. The following weighted analogue (and generalization) of a well-known result by Dirac for unweighted graphs is due to Bondy and Fan. Let G be a 2-connected weighted...
Przybylo, Jakub (2008)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Martin Bača (1990)
Mathematica Slovaca
Similarity:
Shenggui Zhang, Xueliang Li, Hajo Broersma (2001)
Discussiones Mathematicae Graph Theory
Similarity:
A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. The weighted degree sum of any three independent vertices is at least m; 2. w(xz) = w(yz)...
Delorme, C. (1999)
Publications de l'Institut Mathématique. Nouvelle Série
Similarity:
Fulmek, Markus (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Shen, Jian, Yuster, Raphael (2002)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Olivier Baudon, Julien Bensmail, Éric Sopena (2015)
Discussiones Mathematicae Graph Theory
Similarity:
The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct...
Benkart, Georgia, Eng, Oliver (2004)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Mubayi, Dhruv, Rödl, Vojtěch (2004)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Nader Jafari Rad (2011)
The Yugoslav Journal of Operations Research
Similarity: