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 7 Next

Displaying 121 – 140 of 455

Showing per page

Dense Arbitrarily Partitionable Graphs

Rafał Kalinowski, Monika Pilśniak, Ingo Schiermeyer, Mariusz Woźniak (2016)

Discussiones Mathematicae Graph Theory

A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n1, . . . , nk) of positive integers with n1 + ⋯ + nk = n, there exists a partition (V1, . . . , Vk) of the vertex set V (G) such that Vi induces a connected subgraph of order ni for i = 1, . . . , k. In this paper we show that every connected graph G of order n ≥ 22 and with [...] ‖G‖ > (n−42)+12 | | G | | > n - 4 2 + 12 edges is AP or belongs to few classes of exceptional graphs.

Discrete Dirac operators on Riemann surfaces and Kasteleyn matrices

David Cimasoni (2012)

Journal of the European Mathematical Society

Let ∑ be a flat surface of genus g with cone type singularities. Given a bipartite graph Γ isoradially embedded in ∑ , we define discrete analogs of the 2 2 g Dirac operators on ∑ . These discrete objects are then shown to converge to the continuous ones, in some appropriate sense. Finally, we obtain necessary and sufficient conditions on the pair Γ ⊂ ∑ for these discrete Dirac operators to be Kasteleyn matrices of the graph Γ . As a consequence, if these conditions are met, the partition function of the dimer...

Disjoint 5-cycles in a graph

Hong Wang (2012)

Discussiones Mathematicae Graph Theory

We prove that if G is a graph of order 5k and the minimum degree of G is at least 3k then G contains k disjoint cycles of length 5.

Disjoint triangles and quadrilaterals in a graph

Hong Wang (2008)

Open Mathematics

Let n, s and t be three integers with s ≥ 1, t ≥ 0 and n = 3s + 4t. Let G be a graph of order n such that the minimum degree of G is at least (n + s)/2. Then G contains a 2-factor with s + t components such that s of them are triangles and t of them are quadrilaterals.

Distance independence in graphs

J. Louis Sewell, Peter J. Slater (2011)

Discussiones Mathematicae Graph Theory

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number β D ( G ) is the maximum cardinality of a D-independent set. In particular, the independence number β ( G ) = β 1 ( G ) . Along with general results we consider, in particular, the odd-independence number β O D D ( G ) where ODD = 1,3,5,....

Domination, Eternal Domination, and Clique Covering

William F. Klostermeyer, C.M. Mynhardt (2015)

Discussiones Mathematicae Graph Theory

Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and...

Domination in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Let V₁, V₂ be a partition of the vertex set in a graph G, and let γ i denote the least number of vertices needed in G to dominate V i . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value...

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number s d γ ( 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 domination number. Arumugam conjectured that 1 ≤ s d γ ( G ) ≤ 3 for any graph G. We give a counterexample to this conjecture. On the other hand, we show...

Edge Dominating Sets and Vertex Covers

Ronald Dutton, William F. Klostermeyer (2013)

Discussiones Mathematicae Graph Theory

Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.

Currently displaying 121 – 140 of 455