Decomposing infinite 2-connected graphs into 3-connected components.
Digraphs maximal with respect to arc connectivity
Digraphs maximal with respect to connectivity
Directed forests with application to algorithms related to Markov chains
This paper is devoted to computational problems related to Markov chains (MC) on a finite state space. We present formulas and bounds for characteristics of MCs using directed forest expansions given by the Matrix Tree Theorem. These results are applied to analysis of direct methods for solving systems of linear equations, aggregation algorithms for nearly completely decomposable MCs and the Markov chain Monte Carlo procedures.
Directed subgraph complexes.
Distance-Locally Disconnected Graphs
For an integer k ≥ 1, we say that a (finite simple undirected) graph G is k-distance-locally disconnected, or simply k-locally disconnected if, for any x ∈ V (G), the set of vertices at distance at least 1 and at most k from x induces in G a disconnected graph. In this paper we study the asymptotic behavior of the number of edges of a k-locally disconnected graph on n vertices. For general graphs, we show that this number is Θ(n2) for any fixed value of k and, in the special case of regular graphs,...