The Hub Number of Sierpiński-Like Graphs

A set Q⊆V is a hub set of a graph G=(V,E) if, for every pair of vertices u,v∈V∖Q, there exists a path from u to v such that all intermediate vertices are in Q. The hub number of G is the minimum size of a hub set in G. This paper derives the hub numbers of Sierpiński-like graphs including: Sierpiński graphs, extended Sierpiński graphs, and Sierpiński gasket graphs. Meanwhile, the corresponding minimum hub sets are also obtained.     

Global Strong Defensive Alliances of Sierpiński-Like Graphs

A strong alliance in a graph G=(V,E) is a set of vertices S?V satisfying the condition that, for each v∈S, the number of its neighbors, including itself, in S is greater than the number of those neighbors not in S. A strong alliance S is global if S forms a dominating set of G. In this paper, we shall propose a way for finding a minimum global strong alliance for each of those Sierpiński-like graphs. Furthermore, we also derive the exact values of those global strong alliance numbers.     

Contiguous Search Problem in Sierpiński Graphs

In this paper we consider the problem of capturing an intruder in a particular fractal graph, the Sierpiński graph SG _n . The problem consists of having a team of mobile software agents that collaborate in order to capture the intruder. The intruder is a mobile entity that escapes from the team of agents, moving arbitrarily fast inside the network, i.e., traversing any number of contiguous nodes as long as no other agent resides on them. The agents move asynchronously and they know the network topology they are in is a Sierpiński graph SG _n . We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider some variations of the model based on the capabilities of the agents: visibility, where the agents can “see” the state of their neighbors and thus can move autonomously; locality, where the agents can only access local information and thus their moves have to be coordinated by a leader. For each model, we design a capturing strategy and we make some observations. One of our goals is to continue a previous study on what is the impact of visibility on complexity: in this topology we are able to reach an optimal bound on the number of agents required by both cleaning strategies. However, the strategy in the visibility model is fully distributed, whereas the other strategy requires a leader. Moreover, the second strategy requires a higher number of moves and time steps. A preliminary version of this paper has been presented at the 4th International Conference on Fun with Algorithms (FUN’07) 17.     

Crossing Number and Weighted Crossing Number of Near-Planar Graphs

A nonplanar graph G is near-planar if it contains an edge e such that G−e is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hliněny and Salazar (Graph Drawing GD’06). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs.     

The finite difference method for the heat equation on Sierpiński simplices

In the sequel, we extend our previous work on the Minkowski Curve to Sierpiński simplices (Gasket and Tetrahedron), in the case of the heat equation. First, we build the finite difference scheme. Then, we give a theoretical study of the error, compute the scheme error, give stability conditions, and prove the convergence of the scheme. Contrary to existing work, we do not call for approximations of the eigenvalues.     

The Generation of a Sort of Fractal Graphs

We present an approach for generating a sort of fractal graphs by a simple probabilistic logic neuron network and show that the graphs can be represented by a set of compressed codings.An algorithm for quickly finding the codings,i.e.,recognizing the corresponding graphs,is given.The codings are shown to be optimal.The results above possibly give us the clue for studying image compression and pattern recognition.     

The Complexity of Counting Eulerian Tours in?4-regular Graphs

We investigate the complexity of counting Eulerian tours (#ET) and its variations from two perspectives—the complexity of exact counting and the complexity w.r.t. approximation-preserving reductions (AP-reductions, Dyer et al., Algorithmica 38(3):471–500, 2004). We prove that #ET is #P-complete even for planar 4-regular graphs.     

Construction of Simple Path Graphs in Transport Networks: II. Analysis of Graphs’ Biconnectivity

Journal of Computer and Systems Sciences International - The problem of constructing all simple paths in an undirected graph that pairwise connect vertices from the given set is interpreted as...     

Property Testing on k-Vertex-Connectivity of?Graphs

We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called ε-far from k-vertex-connectivity when at least $\frac{\epsilon dn}{2}$ edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is ε-far from k-vertex-connectivity with a probability of at least 2/3. The algorithm runs in $O(d(\frac{c}{\epsilon d})^{k}\log\frac {1}{\epsilon d})$ time (c>1 is a constant) for (k?1)-vertex-connected graphs, and in $O(d(\frac{ck}{\epsilon d})^{k}\log\frac{k}{\epsilon d})$ time (c>1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k≥4.     

Optimal Partitioning and Granularity of Uniform Task Graphs

Task partitioning is an important technique in parallel processing.In this paper,we investigate theoptimal partitioning strategies and granularities of tasks with communications based on several models ofparallel computer systems.Different from the usual approach,we study the optimal partitioning strate-gies and granularities from the viewpoint of minimizing T as well as minimizing NT~2,where N is thenumber of processors used and T is the program execution time using N processors.Our results showthat the optimal partitioning strategies for all cases discussed in this paper are the same——either to as-sign all tasks to one processor or to distribute them among the processors as equally as possible de-pending only on the functions of ratio of running time to communication time R/C.     

Optimal Partitioning and Granularity of Uniform Task Graphs

Task partitioning is an important technique in parallel processing.In this paper,we investigate the optimal partitioning strategies and granularities of tasks with communications based on several models of parallel computer systems.Different from the usual approach,we study the optimal partitioning strategies and granularities from the viewpoint of minimizing T as well as minimizing NT^2,where N is the number of processors used and T is the program execution time using N processors.Our results show that the optimal partitioning strategies for all cases discussed in this paper are the same--either to assign all tasks to one processor or to distribute them among the processors as equally as possible depending only on the functions of ratio of running time to communication time R/C.     

Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth

We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobás, and Sorkin (J. Comb. Theory Ser. B 92(2):199–233, 2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k)⋅n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses 2^3k2+O(k)·n2^{3k^{2}+O(k)}\cdot n arithmetic operations and can be efficiently implemented in parallel.     

The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph G and a subset T\mathcal{T} of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T\mathcal{T} is a set of vertex-disjoint paths ℘ that covers the vertices of G such that the k vertices of T\mathcal{T} are all endpoints of the paths in ℘. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T\mathcal{T} is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112:49–64, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.     

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

In a finite undirected graph, an apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one of the cycle vertices. A graph is apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs, claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination of clique separators with modular decomposition. Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class; the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class.     

Too Much of a Good Thing? The Relationship Between Number of Friends and Interpersonal Impressions on Facebook

A central feature of the online social networking system, Facebook, is the connection to and links among friends. The sum of the number of one's friends is a feature displayed on users' profiles as a vestige of the friend connections a user has accrued. In contrast to offline social networks, individuals in online network systems frequently accrue friends numbering several hundred. The uncertain meaning of friend status in these systems raises questions about whether and how sociometric popularity conveys attractiveness in non-traditional, non-linear ways. An experiment examined the relationship between the number of friends a Facebook profile featured and observers' ratings of attractiveness and extraversion. A curvilinear effect of sociometric popularity and social attractiveness emerged, as did a quartic relationship between friend count and perceived extraversion. These results suggest that an overabundance of friend connections raises doubts about Facebook users' popularity and desirability.     

Finding Induced Paths of Given Parity in Claw-Free Graphs

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in $\mathcal{O}(n^{5})$ time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in $\mathcal{O}(n^{5})$ time and $\mathcal{O}(n^{7})$ time, respectively. We also show that we can decide in $\mathcal{O}(n^{7})$ time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in $\mathcal {O}(n^{7})$ time.     

A proof of image Euler Number formula

1 Introduction In digital image, topological invariant refers to the value, which can keep the image characteristics unchanged when the image flexes freely just like the elastic rubber. The Euler Number is one of the topological characteristics, which can…     

Deciding k-Colorability of P 5-Free Graphs in Polynomial Time

The problem of computing the chromatic number of a P ₅-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer k, there exists a polynomial-time algorithm determining whether or not a P ₅-free graph admits a k-coloring, and finding one, if it does.     

Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs

Given an undirected multigraph G=(V,E), a family $\mathcal{W}Given an undirected multigraph G=(V,E), a family W\mathcal{W} of areas W⊆V, and a target connectivity k≥1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W ? WW\in \mathcal{W} . So far this problem was shown to be NP-complete in the case of k=1 and polynomially solvable in the case of k=2. In this paper, we show that the problem for k≥3 can be solved in O(m+n(k ³+n ²)(p+kn+nlog n)log k+pkn ³log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and p=|W|p=|\mathcal{W}| .