Some topological properties of star graphs: The surface area and volume

The star graph, as an interesting network topology, has been extensively studied in the past. In this paper, we address some of the combinatorial properties of the star graph. In particular, we consider the problem of calculating the surface area and volume of the star graph, and thus answering an open problem previously posed in the literature. The surface area of a sphere with radius i in a graph is the number of nodes in the graph whose distance from a given node is exactly i. The volume of a sphere with radius i in a graph is the number of nodes within distance i from the given node. In this paper, we derive explicit expressions to calculate the surface area and volume in the star graph.     

Lower and upper orientable strong radius and strong diameter of complete k-partite graphs

For two vertices u and v in a strong digraph D, the strong distance sd(u,v) between u and v is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex farthest from v. The strong radius srad(D) (resp. strong diameter sdiam(D)) is the minimum (resp. maximum) strong eccentricity among the vertices of D. The lower (resp. upper) orientable strong radius srad(G) (resp. SRAD(G)) of a graph G is the minimum (resp. maximum) strong radius over all strong orientations of G. The lower (resp. upper) orientable strong diameter sdiam(G) (resp. SDIAM(G)) of a graph G is the minimum (resp. maximum) strong diameter over all strong orientations of G. In this paper, we determine the lower orientable strong radius and diameter of complete k-partite graphs, and give the upper orientable strong diameter and the bounds on the upper orientable strong radius of complete k-partite graphs. We also find an error about the lower orientable strong diameter of complete bipartite graph K_m,n given in [Y.-L. Lai, F.-H. Chiang, C.-H. Lin, T.-C. Yu, Strong distance of complete bipartite graphs, The 19th Workshop on Combinatorial Mathematics and Computation Theory, 2002, pp. 12-16], and give a rigorous proof of a revised conclusion about sdiam(K_m,n).     

On Integral Sum Graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous relative results are also presented.     

On integral sum graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous related results are also presented.     

On minimum power connectivity problems

Given a (directed or undirected) graph with edge costs, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we present polynomial and improved approximation algorithms, as well as inapproximability results, for some classic network design problems under the power minimization criteria. Our main result is for the problem of finding a min-power subgraph that contains k internally-disjoint vs-paths from every node v to a given node s: we give a polynomial algorithm for directed graphs and a logarithmic approximation algorithm for undirected graphs. In contrast, we will show that the corresponding edge-connectivity problems are unlikely to admit even a polylogarithmic approximation.     

Bi-Objective Median Subtree Location Problems

A number of network design problems can be built on the following premise: given an undirected tree network, T, with node set, V, identify a single subtree, t, containing nodes, v, so that the subtree is located optimally with respect to the remaining, subset of unconnected nodes {V–v}. Distances between unconnected nodes and nodes in the subtree t can be defined on paths that are restricted to lie in the larger tree T (the restricted case), or can be defined on paths in an auxiliary complete graph G (the unrestricted case). The unrestricted case represents a class of problems that is not explicitly recognized in the literature, which is of intermediate complexity relative to the widely studied restricted case, and the general problem in which the underlying graph is general. This paper presents the Median Subtree Location Problem (MSLP), formulated as a bicriterion problem that trades off the cost of a subtree, t, against the population-weighted travel distance from the unconnected nodes to nodes on the subtree where both objectives are to be minimized. Integer programs were formulated for the travel restricted and travel unrestricted cases and were tested using linear programming and branch and bound to resolve fractions. Tradeoff curves between cost and travel burden were developed for sample networks.     

On the distance spectral radius of some graphs

For a connected graph, the distance spectral radius is the largest eigenvalue of its distance matrix. In this paper, we determine the unique graph with minimum distance spectral radius among all connected graphs of order n with a given diameter. Moreover, we determine the unique graph with maximum distance spectral radius among the catacondensed hexagonal systems with h hexagons.     

Mobile geometric graphs: detection, coverage and percolation

We consider the following dynamic Boolean model introduced by van den Berg et al. (Stoch. Process. Appl. 69:247–257, 1997). At time 0, let the nodes of the graph be a Poisson point process in ${\mathbb{R}^d}$ with constant intensity and let each node move independently according to Brownian motion. At any time t, we put an edge between every pair of nodes whose distance is at most r. We study three fundamental problems in this model: detection (the time until a target point—fixed or moving—is within distance r of some node of the graph); coverage (the time until all points inside a finite box are detected by the graph); and percolation (the time until a given node belongs to the infinite connected component of the graph). We obtain precise asymptotics for these quantities by combining ideas from stochastic geometry, coupling and multi-scale analysis.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.     

Diameters of random circulant graphs

The diameter of a graph measures the maximal distance between any pair of vertices. The diameters of many small-world networks, as well as a variety of other random graph models, grow logarithmically in the number of nodes. In contrast, the worst connected networks are cycles whose diameters increase linearly in the number of nodes. In the present study we consider an intermediate class of examples: Cayley graphs of cyclic groups, also known as circulant graphs or multi-loop networks. We show that the diameter of a random circulant 2k-regular graph with n vertices scales as n ^1/k , and establish a limit theorem for the distribution of their diameters. We obtain analogous results for the distribution of the average distance and higher moments.     

Observable graphs

An edge-colored directed graph is observable if an agent that moves along its edges from node to node is able to determine his position in the graph after a sufficiently long observation of the edge colors, and without accessing any information about the traversed nodes. When the agent is able to determine his position only from time to time, the graph is said to be partly observable. Observability in graphs is desirable in situations where autonomous agents are moving on a network and they want to localize themselves with limited information. In this paper, we completely characterize observable and partly observable graphs and show how these concepts relate to other concepts in the literature. Based on these characterizations, we provide polynomial time algorithms to decide observability, to decide partial observability, and to compute the minimal number of observations necessary for finding the position of an agent. In particular we prove that in the worst case this minimal number of observations increases quadratically with the number of nodes in the graph. We then consider the more difficult question of assigning colors to a graph so as to make it observable and we prove that two different versions of this problem are NP-complete.     

Optimal gathering protocols on paths under interference constraints

We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d≥1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for 1≤d≤4, in the second case.     

Diameter-essential edges in a graph

The eccentricity e(v) of v is the distance to a farthest vertex from v. The diameter diam(G) is the maximum eccentricity among the vertices of G. The contraction of edge e=uv in G consists of removing e and identifying u and v as a single new vertex w, where w is adjacent to any vertex that at least one of u or v were adjacent to. The graph resulting from contracting edge e is denoted G/e. An edge e is diameter-essential if diam(G/e)<diam(G). Let c(G) denote the number of diameter-essential edges in graph G. In this paper, we study existence and extremal problems for c(G); determine bounds on c(G) in terms of diameter and order; and obtain characterizations of graphs achieving extreme values of c(G).     

On diameter critical graphs

A graph G is diameter k-critical if the graph has diameter k and the deletion of any edge increases its diameter. We show that every diameter 2-critical graph on v vertices has (i) at most 0.27v² edges, and (ii) average edge degree at most $\text{6}\text{5}$v. We also make a conjecture on the maximal number of edges in a diameter k-critical graph.     

Broadcasting secure messages via optimal independent spanning trees in folded hypercubes

Fault-tolerant broadcasting and secure message distribution are important issues for network applications. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and security. An n-dimensional folded hypercube, denoted by FQ_n, is a strengthening variation of hypercube by adding additional links between nodes that have the furthest Hamming distance. In, [12], Ho(1990) proposed an algorithm for constructing n+1 edge-disjoint spanning trees each with a height twice the diameter of FQ_n. Yang et al. (2009), [29] recently proved that Ho’s spanning trees are indeed independent, i.e., any two spanning trees have the same root, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce n+1 independent spanning trees of FQ_n, where the height of each tree is equal to the diameter of FQ_n plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal.     

An algorithm for source location in directed graphs

A polynomial time solution algorithm is described to find a smallest subset R of nodes of a directed graph D=(V,A) such that, for every node v∈V-R, there are k edge-disjoint paths from R to v and there are l edge-disjoint paths from v to R.     

The Chartrand-Schuster conjecture: Graphs with unique distance trees are regular

Let G be a finite connected graph with no cut vertex. A distance tree T is a spanning tree of G which further satisfies the condition that for some vertex v, d_G(v, u) = d_T(v, u) for all u, where d_G(v, u) denotes the distance of u from v in the graph G. The conjecture that if all distance trees of G are isomorphic to each other then G is a regular graph, is settled affirmatively. The conjecture was made by Chartrand and Schuster.     

A Sharp Bound for the Marginal Appendage Number

For a connected graph G, the distance d(u, v) between two vertices u and v is the length of a shortest u − v path in G and the distance d(v) of a vertex v is the sum of the distances between v and all vertices of G. The margin, μ (G), is the subgraph induced by vertices of G having the maximum distance. It is known that every graph is isomorphic to the margin of some graph H. For a graph G, the marginal appendage number is defined as min{p(H) − p(G) ∣ μ(H) = G}. In this paper it is shown that Δ (G) + 2 is a sharp bound for the marginal appendage number.     

On almost distance-regular graphs

Distance-regular graphs are a key concept in Algebraic Combinatorics and have given rise to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distance-regular graphs, we study ‘almost distance-regular graphs’. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distance-regular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walk-regular if the number of closed walks of given length rooted at any given vertex is a constant. One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called m-walk-regularity. Another studied concept is that of m-partial distance-regularity or, informally, distance-regularity up to distance m. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of (?,m)-walk-regularity. We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.     

A characterization of the interval distance monotone graphs

A simple connected graph G is said to be interval distance monotone if the interval I(u,v) between any pair of vertices u and v in G induces a distance monotone graph. A?¨der and Aouchiche [Distance monotonicity and a new characterization of hypercubes, Discrete Math. 245 (2002) 55-62] proposed the following conjecture: a graph G is interval distance monotone if and only if each of its intervals is either isomorphic to a path or to a cycle or to a hypercube. In this paper we verify the conjecture.