Now showing items 1-3 of 3
| 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: | 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: | 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) |
Now showing items 1-3 of 3
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.