Search

The firefighter game problem on locally finite connected graphs was introduced by Bert Hartnell. The game on a graph $G$ can be described as follows: let $f_n$ be a sequence of positive integers; an initial fire starts at a finite set of vertices; at each (integer) time $n\geq 1$, $f_n$ vertices which are not on fire become protected, and then the fire spreads to all unprotected neighbors of vertices on fire; once a vertex is protected or is on fire, it remains so for all time intervals. The graph $G$ has the \emph{$f_n$-containment property} if every initial fire admits an strategy that protects $f_n$ vertices at time $n$ so that the set of vertices on fire is eventually constant. If the graph $G$ has the containment property for a sequence of the form $f_n=Cn^d$, then the graph is said to have \emph{polynomial containment}. In [5], it is shown that any locally finite graph with polynomial growth has polynomial containment; and it is remarked that the converse does not hold. That article also raised the question of whether the equivalence of polynomial growth and polynomial containment holds for Cayley graphs of finitely generated groups. In this short note, we remark how the equivalence holds for elementary amenable groups and for non-amenable groups from results in the literature.

We propose a new type of network location problem for placing multiple but distinct facilities, called the p-service center problem. In this problem, we are to locate p facilities in the graph, each of which provides distinct service required by all vertices. For each vertex, its p-service distance is the summation of its weighted distances to the p facilities. The objective is to minimize the maximum value among the p-service distances of all vertices. In this paper, we show that the p-service center problem on a general graph is NP-hard, and propose a simple approximation algorithm of factor p / c for any integer constant c. Moreover, we study the basic case p = 2 on paths and trees. When the underlying network is a path, we solve the 2-service center problem in O ( n ) time, where n is the number of vertices. When the underlying network is a tree, we give an O ( n 3 ) -time algorithm for the case of nonnegative weights, an O ( n log ⁡ n ) -time algorithm for the case of positive weights, and an O ( n ) -time algorithm for the case of uniform weights.

In this paper, we are concerned with a contact process with a semi-infected state on the complete graph Cn with n vertices. Our model is a special case of a general model introduced by Schinazi in 2003. In our model, each vertex is in one of three states, namely, “healthy,” “semi-infected,” or “fully-infected.” Only fully-infected vertices can infect others. A healthy vertex becomes semi-infected when being infected while a semi-infected vertex becomes fully-infected when being further infected. Each (semi- and fully-) infected vertex becomes healthy at constant rate. Our main result shows a phase transition for the waiting time until extinction of the fully-infected vertices. Conditioned on all the vertices are fully-infected when t = 0, we show that fully-infected vertices survive for exp {O(n)} units of time when the infection rate λ > 4 while they die out in O(log n) units of time when λ < 4.

A disjoint path cover of a graph is a set of pairwise vertex-disjoint paths that altogether cover every vertex of the graph. In this paper, we prove that given k sources, s 1 , …, s k , in an m -dimensional restricted hypercube-like graph with a set F of faults (vertices and/or edges), associated with k positive integers, l 1 , …, l k , whose sum is equal to the number of fault-free vertices, there exists a disjoint path cover composed of k fault-free paths, each of whose paths starts at s i and contains l i vertices for i ∈ { 1 , … , k } , provided | F | + k ≤ m − 1 . The bound, m − 1 , on | F | + k is the best possible.

The channel assignment problem (CAP) which finds an efficient assignment of channels to the transmitters of a wireless network is applicable to cellular mobile system (CMS). There are lots of results on CAP for CMS where the channel separation constraint is represented by a symmetric matrix or a graph. In particular, the Philadelphia instances and the 49-cell system are benchmark CAP for CMS and are treated in many papers. The distance multi-labelling (DM) problem on a graph with weighted vertices is an effective mathematical model of CAP for CMS in which a CMS is represented by a graph with weighted vertices, where a vertex corresponds to a cell with the number of calls on it as its weight. A DM on a graph with weighted vertices is an assignment of a set of non-negative numbers to each vertex. These numbers, which are called labels, represent the channels assigned to the demand calls in each cell. DM is a generalisation of both distance labelling and graph multi-colouring. In this study, the author introduce a new method called the layering method to find a DM on a graph with weighted vertices. Using this method, we obtain optimal DM for two Philadelphia instances. For each of them, the authors obtain a DM according to the range of separation conditions, and it includes known optimal results which are individually obtained under one separation condition.

In this paper, we introduce and investigate the Minimum Eccentricity Shortest Path (MESP) problem in unweighted graphs. It asks for a given graph to find a shortest path with minimum eccentricity. Let n and m denote the number of vertices and the number of edges of a given graph. We demonstrate that: • a minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line; • the MESP problem is NP-hard for planar bipartite graphs with maximum degree 3 and W[2]-hard for general graphs; • a shortest path of minimum eccentricity k can be computed in O ( n 2 k + 2 m ) time; • a 2-approximation, a 3-approximation, and an 8-approximation for the MESP problem can be computed in O ( n 3 ) time, in O ( n m ) time, and in O ( m ) time, respectively; • in a graph with a shortest path of eccentricity k, a k-dominating set can be found in n O ( k ) time.

The coordination encirclements in a graph of Penrose tiling vertices have been investigated based on the analysis of vertice parameters. A strong parameterization of these vertices is developed in the form of a tiling of a parameter set in the region corresponding to different first coordination encirclements of vertices. An algorithm for constructing tilings of a set of parameters determining different coordination encirclements in a graph of Penrose tiling vertices of order n is proposed.

The unique graphs with maximum spectral radius and signless Laplacian spectral radius are determined among trees, unicyclic graphs and bicyclic graphs respectively with fixed numbers of vertices and branch vertices (vertices of degree at least 3) using a unified approach.

A Hamilton -cycle in a k-uniform hypergraph of n-vertex is an ordering of all vertices, combined with an ordered subset C of edges, such that any two consecutive edges share exactly vertices and each edge in C contains k consecutive vertices.A classic result of O. Ore in 1960 is that if the degree sum of any two independent vertices in an n-vertex graph is at least n, then the graph contains a Hamiltonian cycle. Naturally, we consider to generalize it to hypergraphs situation. In this paper, we prove the following theorems. (i) For any n4k2, there is an n-vertex k-uniform hypergraph, with degree sum of any two strongly independent sets of k1 vertices bigger than 2n4(k1), contains no Hamilton l-cycle, 1k1. (ii) If the degree sum of two weakly independent sets of k1 vertices in an n-vertex k-uniform hypergraph is (1+o(1))n, then the hypergraph contains a Hamilton (k1)-cycle, where two distinct sets of k1 vertices are weakly (strongly) independent if there exist no edge containing the union of them (intersecting both of them).

We analyse the size of an independent set in a random graph on $n$ vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as $n \to \infty$, expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges to the jamming constant as $n \to \infty$. The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model., Comment: 25 pages

For a connected graph G , suppose that a fire breaks out at its vertex and a firefighter starts to protect vertices. At each time interval, the firefighter protects k vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. The k -surviving rate ρ k ( G ) of G is defined to be the expected percentage of vertices saved if the fire breaks out at a random vertex. In this note, we consider the surviving rate of 1-planar graphs, and show that every 1-planar graph G has ρ 6 ( G ) > 1 163 .

A connected graph G is said to be k-connected if it has more than k vertices and remains connected whenever fewer than k vertices are deleted. In this paper, we present a tight sufficient condition for a connected graph with fixed minimum degree to be k-connected based on its spectral radius, for sufficiently large order.

The maximum independent set problem is one of the most important problems in theoretical analysis on time and space complexities of exact algorithms. Theoretical improvement on upper bounds on time complexity to solve this problem in low-degree graphs can lead to an improvement on that to the problem in general graphs. In this paper, we derive an upper bound $$O^*(1.1376^n)$$ on the time complexity of a polynomial-space algorithm that solves the maximum independent set problem in an n-vertex graph with degree bounded by 4, improving all previous upper bounds on the time complexity of exact algorithms to this problem. Our algorithm is a branch-and-reduce algorithm and analyzed by using the measure-and-conquer method. To make an amortized analysis of the running time bound, we use an idea of “shift” to save some decrease of the measure from good branches to bad branches. Our algorithm first deals with small vertex cuts and vertices of degree $${\ge }5$$ , which may be created in our algorithm even if the input graph has maximum degree 4, then eliminates cycles of length 3 and 4 containing degree-4 vertices, and finally branches on degree-4 vertices. We invoke an exact algorithm for this problem in graphs with maximum degree 3 directly when the graph has no vertices of degree $${\ge }4$$ . Branching on degree-4 vertices on special local structures will be the bottleneck case, and we carefully design rules of choosing degree-4 vertices to branch on so that the resulting instances after branching decrease the measure effectively in the next step.

We study the problem of structural graph clustering, a fundamental problem in managing and analyzing graph data. Given an undirected unweighted graph, structural graph clustering is to assign vertices to clusters, and to identify the sets of hub vertices and outlier vertices as well, such that vertices in the same cluster are densely connected to each other while vertices in different clusters are loosely connected. In this paper, we develop a new two-step paradigm for scalable structural graph clustering based on our three observations. Then, we present a $\mathsf {pSCAN}$ approach, within the paradigm, aiming to reduce the number of structural similarity computations, and propose optimization techniques to speed up checking whether two vertices are structure-similar. $\mathsf {pSCAN}$ outputs exactly the same clusters as the existing approaches $\mathsf {SCAN}$ and $\mathsf {SCAN\text{++}}$ , and we prove that $\mathsf {pSCAN}$ is worst-case optimal. Moreover, we propose efficient techniques for updating the clusters when the input graph dynamically changes, and we also extend our techniques to other similarity measures, e.g., Jaccard similarity. Performance studies on large real and synthetic graphs demonstrate the efficiency of our new approach and our dynamic cluster maintenance techniques. Noticeably, for the twitter graph with 1 billion edges, our approach takes 25 minutes while the state-of-the-art approach cannot finish even after 24 hours.

The resistance distance between any two vertices of a graph G is defined as the effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index Kf(G) is the sum of the resistance distances between all the pairs of vertices in G. The vertex bipartiteness vb of a graph G is the minimum number of vertices whose deletion from G results in a bipartite graph. In this paper, we characterize the graph having the minimum Kf(G) values among graphs with a fixed number n of vertices and fixed vertex bipartiteness, 1 ź v b ź n - 3 .

A set of vertices S is a resolving set in a graph if each vertex has a unique array of distances to the vertices of S. The natural problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we wish to resolve a set of vertices (up to ź vertices) instead of just one vertex with the aid of the array of distances. The smallest cardinality of a set S resolving at most ź vertices is called ź-set-metric dimension. We study the problem of the ź-set-metric dimension in two infinite classes of graphs, namely, the two dimensional grid graphs and the n-dimensional binary hypercubes. We introduce a way to locate several intruders instead of only one of a resolving set.This prevents mistakes in the location procedure, see Example 2(i).New geometric approach compared to the usual resolving sets (Section 2).We give the complete and optimal results for the two dimensional grid graphs.Optimal results for a very high number of intruders in binary hypercubes.

Let denote the class of c-cyclic graphs with n vertices, girth and pendant vertices. In this paper, we determine the unique extremal graph with largest signless Laplacian spectral radius and Laplacian spectral radius in the class of connected c-cyclic graphs with vertices, girth g and at most pendant vertices, respectively, and the unique extremal graph with largest signless Laplacian spectral radius of when and , and we also identify the unique extremal graph with largest Laplacian spectral radius in in the case and either and g is even or and g is odd. Our results extends the corresponding results of [Sci. Sin. Math. 2010;40:1017–1024, Electron. J. Combin. 2011; 18:p.183, Comput. Math. Appl. 2010;59:376–381, Electron. J. Linear Algebra. 2011;22:378–388 and J. Math. Res. Appl. 2014;34:379–391].

An assignment of weights to the edges and the vertices of a graph is a vertex-coloring total weighting if adjacent vertices have different total weight sums. Of interest in this paper are vertex-coloring total weightings with weight set of cardinality two, a problem motivated by the conjecture that every graph has such a weighting using the weights 1 and 2. Here we prove the existence of such weightings for certain families of graphs using any two different real weights. A related problem where all vertices have unique weight sums is also discussed.

Birkhoff's fundamental theorem on distributive lattices states that for every distributive lattice L there is a poset P L whose lattice of down-sets is order-isomorphic to L . Let G ( L ) denote the cover graph of L . In this paper, we consider the following problems: suppose we are simply given P L . How do we compute the eccentricity of an element of L in G ( L ) ? How about a center and the radius of G ( L ) ? While eccentricity, center and radius computations have long been studied for various classes of graphs, our problems are different in that we are not given the graph explicitly; instead, we only have a structure that implicitly describes the graph. By making use of the comparability graph of P L , we show that all the said problems can be solved efficiently. One of the implications of these results is that a center stable matching, a kind of fair stable matching, can be computed in polynomial time.

In typical graph minimization problems, we consider a graph G with fixed weights on the edges of G. The goal is then to find an optimal vertex or set of vertices with respect to some objective function, for example. We introduce a new framework for graph minimization problems, where the weights on the graph edges are not fixed, but rather must be assigned, and the weight is inversely proportional to the cost paid. The goal is to find a valid assignment for which the resulting weighted graph optimizes the objective function.We present algorithms for finding the optimal budget allocation for the center point problem and for the median point problem on trees. Our algorithms run in linear time, both for the case where a candidate vertex is given as part of the input, and for the case where finding a vertex that optimizes the solution is part of the problem. We also present a hardness result for the center point problem on complete metric graphs, followed by an O ( log 2 ? ( n ) ) approximation algorithm in this setting.

The recently introduced total domination game is studied. This game is played on a graph G by two players, named Dominator and Staller. They alternately take turns choosing vertices of G such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. Dominator's goal is to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game total domination number, źtg(G), of G is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, źźtg(G), of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper it is proved that if G is a graph on n vertices in which every component contains at least three vertices, then źtg(G)≤4n/5 and źźtg(G)≤(4n+2)/5. As a consequence of this result, we obtain upper bounds for both games played on any graph that has no isolated vertices.

A model of a configuration graph on vertices is considered in which the degrees of the vertices are distributed identically and independently according to the law , , , and the number of edges is no greater than . Limit theorems for the number of vertices of a particular degree and for the maximum vertex degree as are established. Bibliography: 18 titles.

Let $T$ be a regular rooted tree. For every natural number $n$, let $B_n$ be the finite subtree of vertices with graph distance at most $n$ from the root. Consider the following forest-fire model on $B_n$: Each vertex can be "vacant" or "occupied". At time $0$ all vertices are vacant. Then the process is governed by two opposing mechanisms: Vertices become occupied at rate $1$, independently for all vertices. Independently thereof and independently for all vertices, "lightning" hits vertices at rate $\lambda(n) > 0$. When a vertex is hit by lightning, its occupied cluster instantaneously becomes vacant. Now suppose that $\lambda(n)$ decays exponentially in $n$ but much more slowly than $1/|B_n|$. We show that then there exist a supercritical time $\tau$ and $\epsilon > 0$ such that the forest-fire model on $B_n$ between time $0$ and time $\tau + \epsilon$ tends to the following process on $T$ as $n$ goes to infinity: At time $0$ all vertices are vacant. Between time $0$ and time $\tau$ vertices become occupied at rate $1$, independently for all vertices. At time $\tau$ all infinite occupied clusters become vacant. Between time $\tau$ and time $\tau + \epsilon$ vertices again become occupied at rate $1$, independently for all vertices. At time $\tau + \epsilon$ all occupied clusters are finite. This process is a dynamic version of self-destructive percolation., Comment: 25 pages

The average eccentricity e c c ( G ) of a graph G is the mean value of eccentricities of all vertices of G . In this paper, we continue the work of Ilic (2012) and resolve a conjecture, obtained by the system AutoGraphiX, about the upper bound on the sum of the average eccentricity and the domination number among connected graphs on n vertices.

In this paper, a new vertex-coloring problem of a fuzzy graph with crisp vertices and fuzzy edges is studied. Membership degree of a fuzzy edge is interpreted as incompatibility degree of its associated incident vertices. This interpretation can be used to define the concept of total incompatibility. Here, unlike the traditional graph coloring problems, two adjacent vertices can receive same colors; these type of vertices and their associated edge are named incompatible vertices and incompatible edge, respectively. In proposed coloring methodology, the total incompatibility of a vertex-coloring is defined as the sum of incompatibility degrees of all incompatible edges. Then, based on the minimum possible degree of total incompatibilities, fuzzy chromatic number of a fuzzy graph is introduced. In order to find an optimal k-coloring, with minimum degree of total incompatibly, firstly a binary programming problem is formulated. Then, a hybrid local search genetic algorithm is designed to solve the large-size problems. Practical uses of the proposed algorithm are illustrated and analyzed by different-size problems. Finally, a cell site assignment problem, as a real world application of the presented fuzzy graph vertex-coloring, is formulated and solved.

Let G be a simple connected graph with vertex set . The connective eccentricity index CEI of a graph is defined as , where , denote the eccentricity and the degree of v, respectively. In this paper, we further study the CEI of trees and unicyclic graphs with several graph constraints, we also determine the extremal graphs.

For any integer k3, we consider the following decision problem. Given a simple graph, does there exist a partition of its vertices into two disjoint sets such that every simple k-cycle of G contains vertices in both of these sets? This problem is NP-hard because it admits a polynomial reduction from NAE 3-SAT. We construct a reduction that is polynomial both in the length of the instance and in k, which answers a recent question of Karpiski.

The focus of research in this paper is to investigate whether a random network whose degree sequence of the vertices is the same as the degree sequence of the vertices in a real-world network would exhibit values for other analysis metrics similar to those of the real-world network. We use the well-known Configuration Model to generate a random network on the basis of the degree sequence of the vertices in a real-world network wherein the degree sequence need not be Poisson-style. The extent of similarity between the vertices of the random network and real-world network with respect to a particular metric is evaluated in the form of the correlation coefficient of the values of the vertices for the metric. We involve a total of 24 real-world networks in this study, with the spectral radius ratio for node degree (measure of variation in node degree) ranging from 1.04 to 3.0 (i.e., from random networks to scale-free networks). We consider a suite of seven node-level metrics and three networklevel metrics for our analysis and identify the metrics for which the degree sequence would be just sufficient to generate random networks that have a very strong correlation (correlation coefficient of 0.8 or above) with that of the vertices in the corresponding real-world networks

The hyper-Wiener index WW(G) is defined as with the summation going over all pairs of vertices in G. In this paper, we determine graphs with the minimum hyper-Wiener index among all the unicyclic graphs with n vertices and k pendent vertices.

The resistance distance was introduced by Klein and Randic as a generalization of the classical distance. The Kirchhoff index Kf (G) of a graph G is the sum of resistance distances between all unordered pairs of vertices. In this paper we determine the extremal graphs with minimal Kirchhoff index among all n-vertex graphs with k cut vertices where 1 ? k < n/2.

The hyper-Wiener index is a kind of extension of the Wiener index, used for predicting physicochemical properties of organic compounds. The hyper-Wiener indexWW(G)is defined asWW(G)=1/2∑u,v∈VGdGu,v+dG2u,vwith the summation going over all pairs of vertices inG, anddGu,vdenotes the distance of the two verticesuandvin the graphG. In this paper, we obtain the second-minimum hyper-Wiener indices among all the trees withnvertices and diameterdand characterize the corresponding extremal graphs.

Let G be a simple, undirected graph. Positive semidefinite (PSD) zero forcing on G is based on the following color-change rule: Let W 1 , W 2 , ? , W k be the sets of vertices of the k connected components in G - B (where B is a set of blue vertices). If w ? W i is the only white neighbor of some b ? B in the graph G B ? W i , then we change w to blue. A minimum positive semidefinite zero forcing set (PSDZFS) is a set of blue vertices that colors the entire graph blue and has minimum cardinality. The PSD propagation time of a PSDZFS B of graph G is the minimum number of iterations that it takes to color the entire graph blue, starting with B blue, such that at each iteration as many vertices are colored blue as allowed by the color-change rule. The minimum and maximum PSD propagation times are taken over all minimum PSD zero forcing sets of the graph. It is conjectured that every propagation time between the minimum and maximum propagation time is attainable by some minimum PSDZFS (this is not the case for the standard color-change rule). Tools are developed that aid in the computation of PSD propagation time. Several graph families and graphs with extreme PSD propagation times ( | G | - 2 , | G | - 1 , 1 , 0 ) are analyzed.

We give asymptotically sharp upper bounds on the radius and diameter of (i) a connected graph, (ii) a connected triangle-free graph, (iii) a connected C4-free graph of given order, minimum degree, and maximum degree. We also give better bounds on the radius and diameter for triangle-free graphs with a given order, minimum degree and a given number of distinct terms in the degree sequence of the graph. Our results improve on old classical theorems by Erd˝os, Pach, Pollack and Tuza [Radius, diameter, and minimum degree, J. Combin. Theory Ser. B 47 (1989), 73-79] on radius, diameter and minimum degree.

In this study, we consider the problem of estimating the diameter of a graph, that is, the maximum distance between any two vertices, in linear time. We address a question posed in the literature—whether there exists an interesting graph class with arbitrarily large cycles for which breadth first search (BFS) would always return high-eccentricity vertices. We answer this question positively, defining a class of graphs that generalizes AT-free graphs and has no bound on the size of induced cycles, yet BFS always returns a vertex whose eccentricity is within a constant difference from the diameter. In addition, we consider the question—also explicitly stated in the literature—whether some variant of the so-called multisweep algorithm would always return a high-eccentricity vertex. We show that the answer is negative by describing a family of graphs for which no variant of multisweep BFS can return a vertex of eccentricity higher than half of the diameter plus a constant.

A set of vertices W is a resolving set of a graph G if every two vertices of G have distinct representations of distances with respect to the set W. The number of vertices in a smallest resolving set is called the metric dimension. This invariant has extensive applications in robotics, since the metric dimension can represent the minimum number of landmarks, which uniquely determine the position of a robot moving in a graph space. Finding the metric dimension of a graph is a non-deterministic polynomial-time hard problem. We present exact values of the metric dimension of several networks, which can be obtained as categorial products of graphs.

The eccentricity e( ) u of a vertex u is the maximum distance of u to any other vertex of G. The distance degree sequence (dds) of a vertex v in a graph G = (V, E) is a list of the number of vertices at distance 1 in that order, where , 2, ..., e(u) e(u) denotes the eccentricity of v in G. Thus, the sequence ( , , , ..., , ...) 0 1 2 j di di di di is the distance degree sequence of the vertex i v in G, where j di denotes the number of vertices at distance j from .i v A graph is distance degree regular (DDR) graph if all the vertices have the same distance degree sequence. A graph is distance degree injective (DDI) graph if no two vertices have the same distance degree sequence. In this paper,we prove that there does not exist cubic DDI graphs of order 16 with diameters 4, 5, 6.

The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size.We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on 2 k - 1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2k vertices is not easier to detect than an independent set on k vertices. In view of linear time upper bounds on the detection of induced path of length two and three, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and an induced paw and its generalizations.We show also that for an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H, resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively.Next, we show that the so-called diamond and its generalizations on k vertices are not easier to detect as induced subgraphs than an independent set on three vertices or an independent set on k vertices, respectively. For C 4 , we give a weaker evidence of its hardness in terms of an independent set on three vertices.Finally, we derive several results relating the complexity of the edge-colored variant of induced subgraph isomorphism to that of the standard variant.

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge-disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree-like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path-like linear decomposition isolating the high degree vertices.

Broadcasting is the process of dissemination of a message from one vertex (called originator) to all other vertices in the graph. This task is accomplished by placing a sequence of calls between neighboring vertices, where one call requires one unit of time and each call involves exactly two vertices. Each vertex can participate in one call per one unit of time. Determination of the broadcast time of a vertex x in arbitrary graph G is NP-complete. Problem can be solved in polynomial time for trees and some subclasses of cactus graphs. In this paper broadcasting in cactus graphs is studied. An algorithm that determines broadcast time of any originator with time complexity O(n) in k-restricted cactus graph (where k is constant) is given. Furthermore, another algorithm which calculates broadcast time for all vertices in k-restricted cactus graph within the same time complexity is outlined. The algorithm also provides an optimal broadcast scheme for every vertex. As a byproduct, broadcast center of a k-restricted cactus graph is computed.

Betweenness centrality is a fundamental measure in social network analysis, expressing the importance or influence of individual vertices in a network in terms of the fraction of shortest paths that pass through them. Exact computation in large networks is prohibitively expensive and fast approximation algorithms are required in these cases. We present two efficient randomized algorithms for betweenness estimation. The algorithms are based on random sampling of shortest paths and offer probabilistic guarantees on the quality of the approximation. The first algorithm estimates the betweenness of all vertices: all approximated values are within an additive factor ɛ from the real values, with probability at least 1-δ. The second algorithm focuses on the top-K vertices with highest betweenness and approximate their betweenness within a multiplicative factor ɛ, with probability at least $1-δ. This is the first algorithm that can compute such approximation for the top-K vertices. We use results from the VC-dimension theory to develop bounds to the sample size needed to achieve the desired approximations. By proving upper and lower bounds to the VC-dimension of a range set associated with the problem at hand, we obtain a sample size that is independent from the number of vertices in the network and only depends on a characteristic quantity that we call the vertex-diameter, that is the maximum number of vertices in a shortest path. In some cases, the sample size is completely independent from any property of the graph. The extensive experimental evaluation that we performed using real and artificial networks shows that our algorithms are significantly faster and much more scalable as the number of vertices in the network grows than previously presented algorithms with similar approximation guarantees.

Let G be a connected graph of order n ? 3 . The remoteness ? = ? ( G ) is the maximum, over all vertices, of the average distance from a vertex to all others. The radius r = r ( G ) is the minimum, over all vertices, of the eccentricity of a vertex. Aouchiche and Hansen (2011) conjectured that ? - r ? 3 - n 4 if n is odd and ? - r ? 2 n - n 2 4 ( n - 1 ) if n is even. In this paper, we confirm this conjecture. In addition, we completely characterize extremal graphs attaining the lower bound.

We consider a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In our model, each link has unit price and each agent tries to minimize its cost, which is either its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two versions of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between the vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between the vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. We take the social cost of the created network to be its diameter, and next we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. When the sum of players' budgets is n-1, the equilibrium graphs are always trees, and we prove that their maximum diameter is Theta(n) and Theta(log n) in MAX and SUM versions, respectively. When each vertex has unit budget (i.e. can establish link to just one vertex), the diameter of any equilibrium graph in either version is Theta(1). We give examples of equilibrium graphs in the MAX version, such that all vertices have positive budgets and yet the diameter is Omega(sqrt(log n)). This interesting (and perhaps counter-intuitive) result shows that increasing the budgets may increase the diameter of equilibrium graphs and hence deteriorate the network structure. Then we prove that every equilibrium graph in the SUM version has diameter 2^O(sqrt(log n)). Finally, we show that if the budget of each player is at least k, then every equilibrium graph in the SUM version is k-connected or has diameter smaller than 4., 28 pages, 3 figures, preliminary version appeared in SPAA'11