Graph partitioning and graph clustering are ubiquitous subtasks in many applications where graphs play an important role. Generally speaking, both techniques aim at the identification of vertex ...subsets with many internal and few external edges. To name only a few, problems addressed by graph partitioning and graph clustering algorithms are: li>What are the communities within an (online) social network? How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer? How must components be organised on a computer chip such that they can communicate efficiently with each other? What are the segments of a digital image? Which functions are certain genes (most likely) responsible for? The 10th DIMACS Implementation Challenge Workshop was devoted to determining realistic performance of algorithms where worst case analysis is overly pessimistic and probabilistic models are too unrealistic. Articles in the volume describe and analyse various experimental data with the goal of getting insight into realistic algorithm performance in situations where analysis fails. This book is published in cooperation with the Center for Discrete Mathematics and Theoretical Computer Science.
For a graph G, a vertex subset S⊆V(G) is said to be Kk-isolating if G−NGS does not contain a clique Kk as a subgraph. The Kk-isolation number of G, denoted by ιk(G), is the minimum cardinality of a ...Kk-isolating set of G. The set S is said to be independent Kk-isolating if S is a Kk-isolating set of G and GS has no edge. The independent Kk-isolation number of G, denoted by ιk′(G), is the minimum cardinality of an independent Kk-isolating set of G. A K1-isolating set (independent K1-isolating set) is clearly a dominating set (independent dominating set). Hence ι1(G)=γ(G), the domination number of G, and ι1′(G)=i(G), the independent domination number of G.
For any graph G of maximum degree Δ(G) and any integer k≥1, we prove that ιk′(G)∕ιk(G)≤Δ(G)−2Δ(G)+2 and that ιk′(G)≤(r−2)(ιk(G)−1)+1 if G is K1,r-free. This respectively generalizes results from Furuya et al. (2014) and from Bollobás and Cockayne (1979) established for k=1.
For integer ... a graph ... is called κ-leaf-connected if ... and given any subset with always has a spanning tree ... such that ... is precisely the set of leaves of ... Thus a graph is ...2-leaf-connected if and only if it is Hamilton-connected. Gurgel and Wakabayashi (1986) provided a sufficient condition based upon the size for a graph to be κ-leaf-connected. In this paper, we present a new condition for κ-leaf-connected graphs which improves the result of Gurgel and Wakabayashi. Meanwhile, we also extend the condition on Hamilton-connected graphs of Zhou and Wang (2017). As applications, sufficient conditions for a graph to be κ-leaf-connected in terms of the (signless Laplacian) spectral radius of G or its complement are obtained.(ProQuest: ... denotes formulae omitted.)
Wavelets on graphs via spectral graph theory Hammond, David K.; Vandergheynst, Pierre; Gribonval, Rémi
Applied and computational harmonic analysis,
03/2011, Volume:
30, Issue:
2
Journal Article
Peer reviewed
Open access
We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph. Our approach is based on defining scaling using the graph ...analogue of the Fourier domain, namely the spectral decomposition of the discrete graph Laplacian
L
. Given a wavelet generating kernel
g and a scale parameter
t, we define the scaled wavelet operator
T
g
t
=
g
(
t
L
)
. The spectral graph wavelets are then formed by localizing this operator by applying it to an indicator function. Subject to an admissibility condition on
g, this procedure defines an invertible transform. We explore the localization properties of the wavelets in the limit of fine scales. Additionally, we present a fast Chebyshev polynomial approximation algorithm for computing the transform that avoids the need for diagonalizing
L
. We highlight potential applications of the transform through examples of wavelets on graphs corresponding to a variety of different problem domains.
In Section 4 of the original paper 'Complex adjacency matrix and energy of digraphs', we incorrectly asserted that the iota energy of digraphs increases with respect to the quasi-order relation ...defined over
if
. In this corrigendum, we point out errors and correct them where possible.
PDF
