Displaying similar documents to “Maxmaxflow and counting subgraphs.”

On the Vertex Separation of Maximal Outerplanar Graphs

Markov, Minko (2008)

Serdica Journal of Computing

Similarity:

We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.

The 1 , 2 , 3-Conjecture And 1 , 2-Conjecture For Sparse Graphs

Daniel W. Cranston, Sogol Jahanbekam, Douglas B. West (2014)

Discussiones Mathematicae Graph Theory

Similarity:

The 1, 2, 3-Conjecture states that the edges of a graph without isolated edges can be labeled from {1, 2, 3} so that the sums of labels at adjacent vertices are distinct. The 1, 2-Conjecture states that if vertices also receive labels and the vertex label is added to the sum of its incident edge labels, then adjacent vertices can be distinguished using only {1, 2}. We show that various configurations cannot occur in minimal counterexamples to these conjectures. Discharging then confirms...

On rainbow connection.

Caro, Yair, Lev, Arie, Roditty, Yehuda, Tuza, Zsolt, Yuster, Raphael (2008)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

On the total domination subdivision numbers in graphs

Seyed Sheikholeslami (2010)

Open Mathematics

Similarity:

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar,...