We introduce the notion of a centroidal locating set of a graph G , that is, a set L of vertices such that all vertices in G are uniquely determined by their relative distances to the vertices of L . A centroidal locating set of G of minimum size is called a centroidal basis, and its size is the centroidal dimension . This notion, which is related to previous concepts, gives a new way of identifying the vertices of a graph. The centroidal dimension of a graph G is lower‐ and upper‐bounded by the metric dimension and twice the location‐domination number of G , respectively. The latter two parameters are standard and well‐studied notions in the field of graph identification. We show that for any graph G with n vertices and maximum degree at least 2, . We discuss the tightness of these bounds and in particular, we characterize the set of graphs reaching the upper bound. We then show that for graphs in which every pair of vertices is connected via a bounded number of paths, , the bound being tight for paths and cycles. We finally investigate the computational complexity of determining for an input graph G , showing that the problem is hard and cannot even be approximated efficiently up to a factor of . We also give an ‐approximation algorithm. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(2), 96–108 2014

A graph $G$ of order $n$ is said to be $\Sigma^{'}$ labeled if there exist a bijection $f:V(G)\rightarrow [n]$ and a constant $c$ such that for all $v\in V(G)$, $\sum_{u\in N[v]} f(u)=c$. The uniqueness of the constant $c$ has been an open question that was posed by Prof. Arumugam at the 2010 IWOGL Conference in Duluth. The question of the uniqueness of such a constant can be extended to arbitrary neighborhoods and to arbitrary sets of labels. For a set $D\subset \mathbb{N}$, let $N_D(v)=\{u\in V(G):d(u,v)\in D\}$, and let $W$ be a multiset of real numbers. Graph $G$ is said to be $(D,W)$-vertex magic if there exists a bijection $g:V(G)\rightarrow W$ such that for all $v\in V(G)$, $\sum_{u\in N_D(v)}g(u)$ is a constant, called the $(D,W)$-vertex magic constant. In this paper we prove that, even for these more general conditions, a $(D,W)$-vertex magic constant will be unique. Moreover, the constant can be determined using a generalization of the fractional domination number of the graph.

Abstract Assume that each vertex of a graph G is the possible location for an “intruder” such as a thief, or a saboteur, a fire in a facility or some possible processor fault in a computer network. A device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v] and to identify at which vertex in N[v] the intruder is located. One must then have a dominating set S ⊆ V(G), a set with ∪v∈SN[v] = V(G), to be able to identify any intruder's location. If any one device can fail to detect the intruder, then one needs a double‐dominating set. This article introduces the study of liar's dominating sets, sets that can identify an intruder's location even when any one device in the neighborhood of the intruder vertex can lie, that is, any one device in the neighborhood of the intruder vertex can misidentify any vertex in its closed neighborhood as the intruder location. Liar's dominating sets lie between double‐dominating sets and triple‐dominating sets because every triple‐dominating set is a liar's dominating set, and every liar's dominating set must double dominate. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Because vertices most central with respect to the center (minimax distance) criterion and the median (minisum distance) criterion can be arbitrarily far apart even in trees, several sequences of central sets have been introduced. Each such sequence is based on an underlying concept that shows the center and median to be part of a spectrum of centrality measures, and several such sequences are examined. The difference between the median criterion and the centroid (maximin voting) criterion is also described, and a centroid-to-median sequence is defined for arbitrary graphs. © 1999 John Wiley & Sons, Inc. Networks 34: 244–249, 1999

The median and centroid of an arbitrary graph G are two different generalizations of the branch weight centroid of a tree. As such, they are closely related, but they can actually be disjoint. On the one hand, they are, for example, always contained in the same block of any connected graph G. However, they can be arbitrarily far apart. Specifically, given any three graphs H, J, and K, and a positive integer k ≥ 4, there exists a graph G with center, median, and centroid subgraphs isomorphic to H, J, and K, respectively, and the distance between any two of these subgraphs is at least k. © 1999 John Wiley & Sons, Inc. Networks 34: 303–311, 1999

In a graph G = (V, E) if we think of each vertex s as the possible location for a guard capable of protecting each vertex in its closed neighborhood N[s], then “domination” requires every vertex to be protected. Thus, S ⊂ V(G) is a dominating set if ∪s∈SN[s] = V(G). For total domination, each guard must, in turn, be protected, so we would want ∪s∈SN(s) = V(G). The (total) domination number γ(G) (γt(G)) is the minimum cardinality taken over all minimal (total) dominating sets of G. We introduce paired-domination for which each guard is assigned another adjacent one, and they are designated as backups for each other, that is, a paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. We show that the paired-domination problem is NP-complete and present bounds on the paired-domination number γp(G). This paper also contains results relating γp(G) to other domination parameters. For example, we note that γ(G) ≤ γt(G) ≤ γp(G) and characterize those triples (a, b, c) of positive integers a ≤ b ≤ c for which there is a graph G having γ(G) = a, γt(G) = b, and γp(G) = c. In addition, we introduce the concept of strong equality of parameters. © 1998 John Wiley & Sons, Inc. Networks 32: 199–206, 1998

Abstract Let G be a probabilistic (n,m) graph in which each vertex exists independently with fixed probability p, 0 < p < 1. Pair‐connected reliability of G, denoted PCv(G;p), is the expected number of connected pairs of vertices in G. An (n,m) graph G is uniformly optimally reliable if PCv(G;p) ≧ PCv(H;p) for all p, 0 < p < 1, over all (n,m) graphs H. It is shown that there does not exist a uniformly optimally reliable (n,m) graph whenever n ≦ m < ∼2n2/9. However, such graphs do exist for some other values of m. In particular, it is established that every complete k‐partite pseudoregular graph on n vertices, 2 ≦ k < n, is uniformly optimally reliable. © 1993 by John Wiley & Sons, Inc.

Abstract We consider probabilistic graphs G = (V, E) in which each edge xy ∈ E fails independently with probability q. The reliability measure studied is pair‐connectivity, the expected number of pairs of connected vertices. We examine how the coefficients of the pair‐connected reliability polynomial are determined by the subgraph structure of G, and we use these results to show that in most cases there does not exist a uniformly optimal n‐vertex, m‐edge graph.

Abstract Locating‐dominating sets are of interest in safeguard applications of graphical models of facilities. A subset S of the vertex set V of a graph G is a dominating set if each vertex u ϵ V ‐ S is adjacent to at least one vertex in S. For each v in V ‐ S let S(v) denote the set of vertices in S which are adjacent to v. A dominating set S is defined to be “locating” if for any two vertices v and w in V ‐ S one has S(v) ≠ S(w) . Sharp bounds on the cardinality of locating‐dominating sets for arbitrary graphs on p vertices and for trees on p vertices are given, and a linear (that is O(P)) algorithm for finding a minimum cardinality locating‐dominating set in an acyclic graph is presented.

Abstract In an earlier paper the measures of centrality in a graph G demonstrated by the center and centroid were unified and generalized, resulting in the definition of the h‐centrum of G and denoted C(G;h) for 1 ≤ h ≤ |V(G)|. When dealing with the h‐centrum one sums the distances from a given vertex u to each of the h vertices farthest from it. Here another way of generalizing the concepts of center and centroid is examined, and the k‐nucleus is defined for G and denoted θk(G). When dealing with the k‐nucleus one sums the distances from a given vertex u to the balls of radius k around each of the other vertices. The centroid of G is θo(G), and the center of G is θr(G), where r is the radius of G. Some relationships between the h‐centra and the k‐nuclei are presented.

In large organizations there is frequently a need to pass information from one place, e.g., the president’s office or company headquarters, to all other divisions, departments or employees. This is often done along organizational reporting lines. Insofar as most organizations are structured in a hierarchical or treelike fashion, this can be described as a process of information dissemination in trees. In this paper we present an algorithm which determines the amount of time required to pass, or to broadcast, a unit of information from an arbitrary vertex to every other vertex in a tree. As a byproduct of this algorithm we determine the broadcast center of a tree, i.e., the set of all vertices from which broadcasting can be accomplished in the least amount of time. It is shown that the subtree induced by the broadcast center of a tree is always a star with two or more vertices. We also show that the problem of determining the minimum amount of time required to broadcast from an arbitrary vertex in an arbitrarygraph is NP-complete.

The problem of finding a minimum k -basis of graph G is that of selecting as small a set B of vertices as possible such that every vertex of G is at distance k or less from some vertex in B . Cockayne, Goodman, and Hedetniemi previously developed a linear algorithm to find a minimum 1-basis (a minimum dominating set) when G is a tree. In this paper the k -basis problem is placed in a more general setting, and a linear algorithm is presented that solves the problem for any forest.

Abstract The Optional Hamiltonian Completion Problem is defined as follows: let the points V of a graph G be partitioned into a set V0 of optional points and a set V1 of non‐optional points; determine the minimum number of new lines which when added to G result in a graph which has a cycle containing every point of V1. This cycle may or may not contain optional points of V0. In this paper we present algorithms for solving this problem for trees, unicyclic graphs and cacti.

article Free Access Share on Advances on the Hamiltonian Completion Problem Authors: S. E. Goodman Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VAView Profile , S. T. Hedetniemi Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VAView Profile , P. J. Slater National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, Iowa National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, IowaView Profile Authors Info & Claims Journal of the ACMVolume 22Issue 3July 1975 pp 352–360https://doi.org/10.1145/321892.321897Published:01 July 1975Publication History 18citation522DownloadsMetricsTotal Citations18Total Downloads522Last 12 Months18Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF