Planar median graphs and cubesquare-graphs Seemann, Carsten R.; Moulton, Vincent; Stadler, Peter F. ...
Discrete Applied Mathematics,
05/2023, Letnik:
331
Journal Article
Recenzirano
Odprti dostop
Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. In this paper we provide several ...novel characterizations of planar median graphs. More specifically, we characterize when a planar graph G is a median graph in terms of forbidden subgraphs and the structure of isometric cycles in G, and also in terms of subgraphs of G that are contained inside and outside of 4-cycles with respect to an arbitrary planar embedding of G. These results lead us to a new characterization of planar median graphs in terms of cubesquare-graphs that is, graphs that can be obtained by starting with cubes and square-graphs, and iteratively replacing 4-cycle boundaries (relative to some embedding) by cubes or square-graphs. As a corollary we also show that a graph is planar median if and only if it can be obtained from cubes and square-graphs by a sequence of “square-boundary” amalgamations. These considerations also lead to an O(nlogn)-time recognition algorithm to compute a decomposition of a planar median graph with n vertices into cubes and square-graphs.
•We propose a new algorithm for the computation of the Fuzzy Generalized Median Graph (FGMG).•We applied the proposed algorithm to the Content-based Document Retrieval (CBDR) problem.•Query and ...database document images are represented by Fuzzy Attributed Relational Graphs (FARGs).•We propose a new FARG embedding method in order to reduce the computation time of the FGMG.•Our algorithm improves the accuracy and speed of document image retrieval processing.
Fuzzy median graph is an important new concept that can represent a set of fuzzy graphs by a representative fuzzy graph prototype. However, the computation of a fuzzy median graph remains a computationally expensive task. In this paper, we propose a new approximate algorithm for the computation of the Fuzzy Generalized Median Graph (FGMG) based on Fuzzy Attributed Relational Graph (FARG) embedding in a suitable vector space in order to capture the maximum information in graphs and to improve the accuracy and speed of document image retrieval processing. In this study, we focus on the application of FGMGs to the Content-based Document Retrieval (CBDR) problem. Experiments on real and synthetic databases containing a large number of FARGs with large sizes show that a CBDR using the FGMG as a dataset representative yields better results than an exhaustive and sequential retrieval in terms of gains in accuracy and time processing.
In this paper, we introduce the Pell graphs, a new family of graphs similar to the Fibonacci cubes. They are defined on certain ternary strings (Pell strings) and turn out to be subgraphs of ...Fibonacci cubes of odd index. Moreover, as well as ordinary hypercubes and Fibonacci cubes, Pell graphs have several interesting structural and enumerative properties. Here, we determine some of them. Specifically, we obtain a canonical decomposition giving a recursive structure, some basic properties (bipartiteness and existence of maximal matchings), some metric properties (radius, diameter, center, periphery, medianicity), some properties on subhypercubes (cube coefficients and polynomials, cube indices, decomposition in subhypercubes), and, finally, the distribution of the degrees.
In this paper, we study structures such as distributive lattices, distributive semilattices, and median graphs from an algorithmic point of view. Such structures are very useful in classification and ...phylogeny for representing lineage relationships for example. A distributive lattice can be considered as a median graph while a distributive ∨-semilattice can be considered as a median graph provided that some conditions holding on triple of elements are satisfied. Starting from a lattice structure with different representations, we study the problem of building a median graph from such structures. We make precise and propose algorithms for checking how a lattice can be distributive and can be a median graph. Then, we adapt the problem to semilattices as a lattice where the bottom element is removed is a ∨-semilattice. We also state the problem in terms of Formal Concept Analysis and the representation of a lattice as a formal context, i.e., a binary table. Moreover, we also propose as input a system of implications such as the Duquenne-Guigues basis of a lattice, and we study how to compute such a basis for a distributive semilattice. In the paper, we provide algorithms and examples which illustrate the difficulties related to these different classification tasks. In particular, the minimality of the output lattices is a condition which is hard to ensure and which cannot be always achieved.
The modular decomposition of a symmetric map δ:X×X→Υ (or, equivalently, a set of pairwise-disjoint symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural ...construction to capture key features of δ in terms of a labeled tree. A map δ is explained by a vertex-labeled rooted tree (T,t) if the label δ(x,y) coincides with the label of the lowest common ancestor of x and y in T, i.e., if δ(x,y)=t(lca(x,y)). Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be explained in this manner. Here we consider rooted median graphs as a generalization of (modular decomposition) trees to explain symmetric maps. We derive a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map δ.
In this paper, we study the Steiner hyper-Wiener index of a graph, which is obtained from the standard hyper-Wiener index by replacing the classical graph distance with the Steiner distance. It is ...shown how this index is related to the Steiner Hosoya polynomial, which generalizes similar result for the standard hyper-Wiener index. Next, we show how the Steiner 3-hyper-Wiener index of a modular graph can be expressed by using the classical graph distances. As the main result, a method for computing this index for median graphs is developed. Our method makes computation of the Steiner 3-hyper-Wiener index much more efficient. Finally, the method is used to obtain the closed formulas for the Steiner 3-Wiener index and the Steiner 3-hyper-Wiener index of grid graphs.
The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to ...compute medians in median graphs. We also present a linear time algorithm to compute medians in the associated ℓ1-cube complexes. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes) via Lexicographic Breadth First Search (LexBFS). We show that any LexBFS ordering of the vertices of a median graph satisfies the following fellow traveler property: the parents of any two adjacent vertices are also adjacent. Using the fast computation of the Θ-classes, we also compute the Wiener index (total distance) in linear time and the distance matrix in optimal quadratic time.
The generalized Fibonacci cube Qh(f) is the graph obtained from the h-cube Qh by removing all vertices that contain a given binary string f as a substring. If G is an induced subgraph of Qh, then the ...cube-complement of G is the graph induced by the vertices of Qh which are not in G. In particular, the cube-complement of a generalized Fibonacci cube Qh(f) is the subgraph of Qh induced by the set of all vertices that contain f as a substring. The questions whether a cube-complement of a generalized Fibonacci cube is (i) connected, (ii) an isometric subgraph of a hypercube or (iii) a median graph are studied. Questions (ii) and (iii) are completely solved, i.e. the sets of binary strings that allow a graph of this class to be an isometric subgraph of a hypercube or a median graph are given. The cube-complement of a daisy cube is also studied.
Shortcut graphs and groups Hoda, Nima
Transactions of the American Mathematical Society,
04/2022, Letnik:
375, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We introduce shortcut graphs and groups. Shortcut graphs are graphs in which cycles cannot embed without metric distortion. Shortcut groups are groups which act properly and cocompactly on shortcut ...graphs. These notions unify a surprisingly broad family of graphs and groups of interest in geometric group theory and metric graph theory, including: the 1-skeletons of systolic and quadric complexes (in particular finitely presented C(6) and C(4)-T(4) small cancellation groups), 1-skeletons of finite dimensional \operatorname {CAT}(0) cube complexes, hyperbolic graphs, standard Cayley graphs of finitely generated Coxeter groups and the standard Cayley graph of the Baumslag-Solitar group \operatorname {BS}(1,2). Most of these examples satisfy a strong form of the shortcut property.
The shortcut properties also have important geometric group theoretic consequences. We show that shortcut groups are finitely presented and have exponential isoperimetric and isodiametric functions. We show that groups satisfying the strong form of the shortcut property have polynomial isoperimetric and isodiametric functions.
Injective Split Systems Hellmuth, M.; Huber, K. T.; Moulton, V. ...
Graphs and combinatorics,
08/2023, Letnik:
39, Številka:
4
Journal Article
Recenzirano
Odprti dostop
A split system
S
on a finite set
X
,
|
X
|
≥
3
, is a set of bipartitions or splits of
X
which contains all splits of the form
{
x
,
X
-
{
x
}
}
,
x
∈
X
. To any such split system
S
we can associate ...the Buneman graph
B
(
S
)
which is essentially a median graph with leaf-set
X
that displays the splits in
S
. In this paper, we consider properties of injective split systems, that is, split systems
S
with the property that
med
B
(
S
)
(
Y
)
≠
med
B
(
S
)
(
Y
′
)
for any 3-subsets
Y
,
Y
′
in
X
, where
med
B
(
S
)
(
Y
)
denotes the median in
B
(
S
)
of the three elements in
Y
considered as leaves in
B
(
S
)
. In particular, we show that for any set
X
there always exists an injective split system on
X
, and we also give a characterization for when a split system is injective. We also consider how complex the Buneman graph
B
(
S
)
needs to become in order for a split system
S
on
X
to be injective. We do this by introducing a quantity for |
X
| which we call the injective dimension for |
X
|, as well as two related quantities, called the injective 2-split and the rooted-injective dimension. We derive some upper and lower bounds for all three of these dimensions and also prove that some of these bounds are tight. An underlying motivation for studying injective split systems is that they can be used to obtain a natural generalization of symbolic tree maps. An important consequence of our results is that any three-way symbolic map on
X
can be represented using Buneman graphs.
PDF
