Explore chapters and articles related to this topic
DTN Coding
Published in Aloizio Pereira da Silva, Scott Burleigh, Katia Obraczka, Delay and Disruption Tolerant Networks, 2019
Marius Feldmann, Felix Walter, Tomaso de Cola, Gianluigi Liva
Another graph property that will condition the performance of an LDPC code under iterative decoding is the graph girth. A cycle in a bipartite graph is a sequence of edges leading to closed path where each node belonging to the cycle is visited once. The length of a cycle is given by the number of edges composing the cycle. The girth g of graph G is the length of its shortest cycle.
Graph theory
Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022
Joanna A. Ellis-Monaghan, Iain Moffatt
A walk in a graph G=(V,E) is a sequence W=v0e1v1⋯vl−1elvl such that ei∈E and ei=(vi−1,vi), for each i. The number of edges in a walk is its length, v0 is the initial vertex, vl is the terminal vertex, and W is a v0vl -walk. The walk W is closed if v0=vl, is a trail if each edge in it is distinct, a circuit if it is a closed trail, a path if each vertex and edge is distinct, and a cycle if v0=vl, but otherwise each vertex and edge is distinct. Walks are often specified by their subsequence of vertices (even when the graph is not simple) if the choice of which parallel edges are taken as the walk is traversed is not important. The girth of a graph is the length of a shortest cycle in it. The distance between two vertices is the length of a shortest path between them. An edge is a chord of a cycle if it is not in the cycle, but its two ends are. A graph that consists of the vertices and edges of a cycle (respectively, path) is also called a cycle (respectively, path). In this setting a cycle of length m is denoted Cm, and a path of length m is denoted Pm.
On the index of convergence of a class of Boolean matrices with structural properties
Published in International Journal of Control, 2021
Guilherme Ramos, Sérgio Pequito, Carlos Caleiro
Next, we introduce some graph theoretic notions (Bollobás, 2012). Let be a digraph, a walk of size from vertex u to vertex v is a sequence of vertices s.t. for . The length of a walk is its size, i.e. the length of is k. A path is a walk that does not repeat vertices. Further, given a path , we say that the edge is an edge before the edge , for . Conversely, we say that the edge is an edge after the edge , for . A cycle in , , is a path together with . The girth of is the shortest length of a cycle contained in the . If does not have cycles, then it is a directed acyclic graph (DAG). A self-loop DAG is a digraph with a self-loop in each node s.t. by removing the self-loops we obtain a DAG. A directed tree is a DAG in which a node is assigned to be the root, and there is exactly one path from the root to each node. A directed r-tree is a directed tree s.t. each node has at most r outgoing edges. In a directed tree, a leaf is a node without outgoing edges. A balanced directed r-tree is a directed r-tree s.t. the lengths of any two paths between the root to a leaf differ by at most 1. A self-loop balanced directed r-tree is a digraph such that if we remove the self-loops then we obtain a balanced directed r-tree. A self-loop directed r-tree is a digraph with a self-loop in each node s.t. we obtain a directed r-tree if we remove the self-loops.