Now showing items 1-14 of 14
| Abstract: | Almost self-centered graphs were recently introduced as the graphs with exactly two non-central vertices. In this paper we characterize almost selfcentered graphs among median graphs and among chordal graphs. In the first case P4 and the graphs obtained from hypercubes by attaching to them a single leaf are the only such graphs. Among chordal graph the variety of almost self-centered graph is much richer, despite the fact that their diameter is at most 3. We also discuss almost self-centered graphs among partial cubes and among k-chordal graphs, classes of graphs that generalize median and chordal graphs, respectively. Characterizations of almost self-centered graphs among these two classes seem elusive |
| Description: | TAIWANESE JOURNAL OF MATHEMATICS Vol. 16, No. 5, pp. 1911-1922, October 2012 |
| URI: | http://dyuthi.cusat.ac.in/purl/4213 |
| Files | Size |
|---|---|
| Almost Self-Centered Median And Chordal Graphs.pdf | (225.6Kb) |
| Abstract: | An antimedian of a pro le = (x1; x2; : : : ; xk) of vertices of a graph G is a vertex maximizing the sum of the distances to the elements of the pro le. The antimedian function is de ned on the set of all pro les on G and has as output the set of antimedians of a pro le. It is a typical location function for nding a location for an obnoxious facility. The `converse' of the antimedian function is the median function, where the distance sum is minimized. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper such a characterization is obtained for the two classes of graphs on which the antimedian is well-behaved: paths and hypercubes. |
| Description: | Discrete Mathematics, Algorithms and Applications |
| URI: | http://dyuthi.cusat.ac.in/purl/4201 |
| Files | Size |
|---|---|
| Axiomatic Chara ... n Paths and Hypercubes.pdf | (173.6Kb) |
| Abstract: | The median (antimedian) set of a profile π = (u1, . . . , uk) of vertices of a graphG is the set of vertices x that minimize (maximize) the remoteness i d(x,ui ). Two algorithms for median graphs G of complexity O(nidim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes |
| Description: | Algorithmica (2010) 57: 207–216 DOI 10.1007/s00453-008-9200-4 |
| URI: | http://dyuthi.cusat.ac.in/purl/4193 |
| Files | Size |
|---|---|
| Computing median and antimedian sets in median.pdf | (290.4Kb) |
| Abstract: | The median problem is a classical problem in Location Theory: one searches for a location that minimizes the average distance to the sites of the clients. This is for desired facilities as a distribution center for a set of warehouses. More recently, for obnoxious facilities, the antimedian was studied. Here one maximizes the average distance to the clients. In this paper the mixed case is studied. Clients are represented by a profile, which is a sequence of vertices with repetitions allowed. In a signed profile each element is provided with a sign from f+; g. Thus one can take into account whether the client prefers the facility (with a + sign) or rejects it (with a sign). The graphs for which all median sets, or all antimedian sets, are connected are characterized. Various consensus strategies for signed profiles are studied, amongst which Majority, Plurality and Scarcity. Hypercubes are the only graphs on which Majority produces the median set for all signed profiles. Finally, the antimedian sets are found by the Scarcity Strategy on e.g. Hamming graphs, Johnson graphs and halfcubes |
| Description: | Ars Math. Contemp. 6 (2013) 127–145 |
| URI: | http://dyuthi.cusat.ac.in/purl/4234 |
| Files | Size |
|---|---|
| Consensus strat ... ned profiles on graphs.pdf | (315.9Kb) |
| Abstract: | Given a graph G and a set X ⊆ V(G), the relative Wiener index of X in G is defined as WX (G) = {u,v}∈X 2 dG(u, v) . The graphs G (of even order) in which for every partition V(G) = V1 +V2 of the vertex set V(G) such that |V1| = |V2| we haveWV1 (G) = WV2 (G) are called equal opportunity graphs. In this note we prove that a graph G of even order is an equal opportunity graph if and only if it is a distance-balanced graph. The latter graphs are known by several characteristic properties, for instance, they are precisely the graphs G in which all vertices u ∈ V(G) have the same total distance DG(u) = v∈V(G) dG(u, v). Some related problems are posed along the way, and the so-called Wiener game is introduced. |
| Description: | Discrete Optimization 12 (2014) 150–154 |
| URI: | http://dyuthi.cusat.ac.in/purl/4220 |
| Files | Size |
|---|---|
| Equal opportuni ... raphs, and Wiener game.pdf | (367.3Kb) |
| Abstract: | Following the Majority Strategy in graphs, other consensus strategies, namely Plurality Strategy, Hill Climbing and Steepest Ascent Hill Climbing strategies on graphs are discussed as methods for the computation of median sets of pro¯les. A review of algorithms for median computation on median graphs is discussed and their time complexities are compared. Implementation of the consensus strategies on median computation in arbitrary graphs is discussed |
| Description: | Report/Econometric Institute, Erasmus University Rotterdam,EI 2007-34 |
| URI: | http://dyuthi.cusat.ac.in/purl/4218 |
| Files | Size |
|---|---|
| Median computat ... g consensus strategies.pdf | (195.4Kb) |
| Abstract: | The median of a profile = (u1, . . . , uk ) of vertices of a graph G is the set of vertices x that minimize the sum of distances from x to the vertices of . It is shown that for profiles with diameter the median set can be computed within an isometric subgraph of G that contains a vertex x of and the r -ball around x, where r > 2 − 1 − 2 /| |. The median index of a graph and r -joins of graphs are introduced and it is shown that r -joins preserve the property of having a large median index. Consensus strategies are also briefly discussed on a graph with bounded profiles. |
| Description: | Discrete Applied Mathematics 156 (2008) 2882–2889 |
| URI: | http://dyuthi.cusat.ac.in/purl/4216 |
| Files | Size |
|---|---|
| The median func ... with bounded profiles.pdf | (410.2Kb) |
| Abstract: | A periphery transversal of a median graph G is introduced as a set of vertices that meets all the peripheral subgraphs of G. Using this concept, median graphs with geodetic number 2 are characterized in two ways. They are precisely the median graphs that contain a periphery transversal of order 2 as well as the median graphs for which there exists a profile such that the remoteness function is constant on G. Moreover, an algorithm is presented that decides in O(mlog n) time whether a given graph G with n vertices and m edges is a median graph with geodetic number 2. Several additional structural properties of the remoteness function on hypercubes and median graphs are obtained and some problems listed |
| Description: | University of Ljubljana Institute of Mathematics, Physics and Mechanics Department of Mathematics Preprint series, Vol. 46 (2008), 1046 |
| URI: | http://dyuthi.cusat.ac.in/purl/4237 |
| Files | Size |
|---|---|
| Median Graphs, ... nd Geodetic Number Two.pdf | (256.4Kb) |
| Abstract: | For a set S of vertices and the vertex v in a connected graph G, max x2S d(x, v) is called the S-eccentricity of v in G. The set of vertices with minimum S-eccentricity is called the S-center of G. Any set A of vertices of G such that A is an S-center for some set S of vertices of G is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, Km,n, Kn −e, wheel graphs, odd cycles and symmetric even graphs and enumerate them for many of these graph classes. We also introduce the concept of center number which is defined as the number of distinct center sets of a graph and determine the center number of some graph classes |
| Description: | arXiv preprint arXiv:1312.3182 |
| URI: | http://dyuthi.cusat.ac.in/purl/4226 |
| Files | Size |
|---|---|
| On The Center S ... of Some Graph Classes.pdf | (198.9Kb) |
| Abstract: | The set of vertices that maximize (minimize) the remoteness is the antimedian (median) set of the profile. It is proved that for an arbitrary graph G and S V (G) it can be decided in polynomial time whether S is the antimedian set of some profile. Graphs in which every antimedian set is connected are also considered. |
| URI: | http://dyuthi.cusat.ac.in/purl/4217 |
| Files | Size |
|---|---|
| On the generali ... blemantimedian subsets.pdf | (142.4Kb) |
| Abstract: | A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x 2 V.G/ the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O.mlog n/ time whether G is a median graph with geodetic number 2 |
| Description: | Discrete Applied Mathematics 157 (2009) 3679- 3688 |
| URI: | http://dyuthi.cusat.ac.in/purl/4197 |
| Files | Size |
|---|---|
| On the remoteness function in median graphs.pdf | (609.5Kb) |
| Abstract: | The Majority Strategy for finding medians of a set of clients on a graph can be relaxed in the following way: if we are at v, then we move to a neighbor w if there are at least as many clients closer to w than to v (thus ignoring the clients at equal distance from v and w). The graphs on which this Plurality Strategy always finds the set of all medians are precisely those for which the set of medians induces always a connected subgraph |
| Description: | Report/Econometric Institute, Erasmus University Rotterdam |
| URI: | http://dyuthi.cusat.ac.in/purl/4208 |
| Files | Size |
|---|---|
| The Plurality Strategy on Graphs.pdf | (149.0Kb) |
| Abstract: | The distance DG(v) of a vertex v in an undirected graph G is the sum of the distances between v and all other vertices of G. The set of vertices in G with maximum (minimum) distance is the antimedian (median) set of a graph G. It is proved that for arbitrary graphs G and J and a positive integer r 2, there exists a connected graph H such that G is the antimedian and J the median subgraphs of H, respectively, and that dH(G, J) = r. When both G and J are connected, G and J can in addition be made convex subgraphs of H. |
| Description: | Networks vol 56(2),pp 90-94 |
| URI: | http://dyuthi.cusat.ac.in/purl/4203 |
| Files | Size |
|---|---|
| Simultaneous Em ... d Antimedian Subgraphs.pdf | (146.2Kb) |
| Abstract: | A graph G is strongly distance-balanced if for every edge uv of G and every i 0 the number of vertices x with d.x; u/ D d.x; v/ 1 D i equals the number of vertices y with d.y; v/ D d.y; u/ 1 D i. It is proved that the strong product of graphs is strongly distance-balanced if and only if both factors are strongly distance-balanced. It is also proved that connected components of the direct product of two bipartite graphs are strongly distancebalanced if and only if both factors are strongly distance-balanced. Additionally, a new characterization of distance-balanced graphs and an algorithm of time complexity O.mn/ for their recognition, wheremis the number of edges and n the number of vertices of the graph in question, are given |
| Description: | European Journal of Combinatorics 30 (2009) 1048- 1053 |
| URI: | http://dyuthi.cusat.ac.in/purl/4198 |
| Files | Size |
|---|---|
| Strongly distan ... phs and graph products.pdf | (373.0Kb) |
Now showing items 1-14 of 14
Dyuthi Digital Repository Copyright © 2007-2011 Cochin University of Science and Technology. Items in Dyuthi are protected by copyright, with all rights reserved, unless otherwise indicated.