A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. We consider total dominating sets of minimum cardinality which have the additional property that distinct vertices of V are totally dominated by distinct subsets of the total dominating set.

A coalition in a graph G =(V, E) consists of two disjoint sets of vertices V1 and V2, neither of which is a dominating set of G but whose union V1 ∪ V2 is a dominating set of G.A coalition partition in a graph G of order n = |V| is a vertex partition π= {V1, V2,⋯, Vk} of V such that every set Vi either is a dominating set consisting of a single vertex of degree n - 1, or is not a dominating set but forms a coalition with another set Vj which is not a dominating set. Associated with every coalition partition πof a graph G is a graph called the coalition graph of G with respect to π, denoted CG(G, π), the vertices of which correspond one-to-one with the sets V1, V2,⋯, Vk of πand two vertices are adjacent in CG(G, π) if and only if their corresponding sets in πform a coalition. In this paper we study coalition graphs, focusing on the coalition graphs of paths, cycles, and trees. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely what they are. On the other hand, we show that there are infinitely many coalition graphs of trees and characterize this family of graphs.

No description available.

A set of vertices in a graph G is a global dominating set of G if it dominates both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications (edge removal, vertex removal, and edge addition) on the global domination number. In particular, for each graph modification, we study the global domination stable trees, that is, the trees whose global domination number remains the same upon the modification. We characterize these stable trees having small global domination numbers.

A set of vertices in a graph G is a global dominating set of G if it dominates both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications (edge removal, vertex removal, and edge addition) on the global domination number. In particular, for each graph modification, we study the global domination stable trees, that is, the trees whose global domination number remains the same upon the modification. We characterize these stable trees having small global domination numbers.

A set S of vertices in a graph G=(V,E) is a total dominating set of G if every vertex of V is adjacent to some vertex in S. In this thesis, we consider total dominating sets of minimum cardinality which have the additional property that distinct vertices of V are totally dominated by distinct subsets of the total dominating set.

This thesis considers a novel problem of obtaining global channel state information (CSI) at every node in an ad-hoc wireless network. A class of protocols for dissemination and estimation are developed which attempt to minimize the staleness of the estimates throughout the network. This thesis also provides an optimal protocol for CSI dissemination in networks with complete graph topology and a near optimal protocol in networks having incomplete graph topology. In networks with complete graph topology, the protocol for CSI dissemination is shown to have a resemblance to finding Eulerian tours in complete graphs. For networks having incomplete graph topology, a lower bound on maximum staleness is given and a near optimal algorithm based on finding minimum connected dominating sets and proper scheduling is described in this thesis.

This thesis considers a novel problem of obtaining global channel state information (CSI) at every node in an ad-hoc wireless network. A class of protocols for dissemination and estimation are developed which attempt to minimize the staleness of the estimates throughout the network. This thesis also provides an optimal protocol for CSI dissemination in networks with complete graph topology and a near optimal protocol in networks having incomplete graph topology. In networks with complete graph topology, the protocol for CSI dissemination is shown to have a resemblance to finding Eulerian tours in complete graphs. For networks having incomplete graph topology, a lower bound on maximum staleness is given and a near optimal algorithm based on finding minimum connected dominating sets and proper scheduling is described in this thesis.

Broadcasting is a fundamental primitive in local area networks (LANs).Operations of many data link protocols, for example, ARP (Address Resolution Protocol) and IGMP (Internet Group Management Protocol), must rely on this LAN primitive. To develop the broadcasting service in mobile ad hoc wireless LANs (WLANs) is a challenge. This is because a mobile ad hoc WLAN is a multi-hop wireless network in which messages may travel along several links from the source to the destination via a certain path. Additionally, there is no fixed network topology because of host moving. Furthermore, the broadcast nature of a radio channel makes a packet be transmitted by a node to be able to reach all neighbors. Therefore, the total number of transmissions (forward nodes) is generally used as the cost criterion for broadcasting. The problem of finding the minimum number of forward nodes in a static radio network is NP-complete. Almost all previous works, therefore, for broadcasting in the WLAN are focusing on finding approximation approaches in a, rather than, environment. In this paper, we propose a novel distributed protocol in WLANs to significantly reduce or eliminate the communication overhead in addition to maintaining positions of neighboring nodes. The important features of our proposed protocol are the adaptability to dynamic network topology change and the localized and parameterless behavior. The reduction in communication overhead for broadcasting operation is measured experimentally. From the simulation results, our protocol not only has the similar performance as the approximation approaches in the static network, but also outperforms existing ones in the adaptability to host moving.

For a subset of vertices S in a graph G, if v ∈ S and w ∈ V - S, then the vertex w is an external private neighbor of v (with respect to S) if the only neighbor of w in S is v. A dominating set S is a private dominating set if each v ∈ S has an external private neighbor. Bollóbas and Cockayne (Graph theoretic parameters concerning domination, independence and irredundance. J. Graph Theory 3 (1979) 241-250) showed that every graph without isolated vertices has a minimum dominating set which is also a private dominating set. We define a graph G to be a private domination graph if every minimum dominating set of G is a private dominating set. We give a constructive characterization of private domination trees.