A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n24 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.

In this article, I locate the Critical Theoretic and Republican themes of misrecognition and domination in transnational democracy, viewed as an emancipatory project. Contrary to John Dryzek, I argue that transnational democracy requires an appropriate account of mutual recognition and personal integrity in order to ground the emancipatory dimension of this project, especially given Dryzek's analysis of transnational contests in forming personal identifications. Beyond this, I argue that the same themes are needed to supplement James Bohman's account of the normative powers of dominated persons to initiate deliberation in circumstances of injustice. Primarily, my claim has been that the idea of personal integrity remains essential not only to motivating the project of transnational democracy, but also modifying the appeal to normative powers in the interest of enabling dominated persons to enter into communicative relationships and engage in public processes of critical self-examination.

A total dominating set of a graph G with no isolated vertex is a set 5 of vertices of G such that every vertex is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set in G. In this paper, we present several upper bounds on the total domination number in terms of the minimum degree, diameter, girth and order.

Hegel may be read as endorsing a republican conception of freedom as non-domination. This may then be allied to an expressive conception of freedom not as communal integration and non-alienation, but rather as the development of new powers and capabilities. To this extent, he may be understood as occupying a position between nondomination and expressive freedom. This not only informs contemporary discussions of republicanism and democracy, but also suggests a ‘capabilities solution’ to the otherwise intractable problem of the rabble.

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well known vertex covering and dominating set problems in graphs (see SIAM J. Discrete Math. 15(4) (2002), 519-529). A set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph is its power domination number. We investigate the power domination number of a block graph.

A global strong defensive alliance in a graph G = (V, E) is a dominating set S of G satisfying the condition that for every vertex ∈ S, the number of neighbors v has in S is at least as large as the number of neighbors it has in V - S. Because of such an alliance, the vertices in S, agreeing to mutually support each other, have the strength of numbers to be able to defend themselves from the vertices in V - S. The global strong alliance number is the minimum cardinality of a global strong defensive alliance in G. We provide a constructive characterization of trees with equal domination and global strong alliance number.

A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G - v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γ t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k≤8 and provide an example which shows that the maximum diameter is in general at least 5k/3 - O(1).

Given a digraph D = (V, A), with vertex set V and arc set A, a set S ⊆ V is a dominating set if for every vertex v in V \ S, there are a vertex u in S and an arc (u, v) from u to v. In this chapter we consider the counterparts in directed graphs of independent, dominating, independent dominating, and total dominating sets in undirected graphs.

For a graph G=(V,E) and a set S⊆V, the boundary of S is the set of vertices in V∖S that have a neighbor in S. A non-empty set S⊆V is a distribution center if for every vertex v in the boundary of S, v is adjacent to a vertex in S, say u, where u has at least as many neighbors in S as v has in V∖S. The distribution center number of a graph G is the minimum cardinality of a distribution center of G. We introduce distribution centers as graph models for supply–demand type distribution. We determine the distribution center number for selected families of graphs and give bounds on the distribution center number for general graphs. Although not necessarily true for general graphs, we show that for trees the domination number and the maximum degree are upper bounds on the distribution center number.

In this thesis, we introduce Roman domination cover rubbling as an extension of domination cover rubbling. We define a parameter on a graph $G$ called the \textit{Roman domination cover rubbling number}, denoted $\rho_{R}(G)$, as the smallest number of pebbles, so that from any initial configuration of those pebbles on $G$, it is possible to obtain a configuration which is Roman dominating after some sequence of pebbling and rubbling moves. We begin by characterizing graphs $G$ having small $\rho_{R}(G)$ value. Among other things, we also obtain the Roman domination cover rubbling number for paths and give an upper bound for the Roman domination cover rubbling number of a tree.