Results 11 to 20 of about 405,092 (308)
Toeplitz graph decomposition [PDF]
Transactions on Combinatorics, 2012 Let $n,t_1,...,t_k$ be distinct positive integers. A Toeplitz graph $G=(V, E)$ denoted by $T_n$ is a graph, where $V ={1,...,n}$ and $E= {(i,j) : |i-j| in {t_1,...,t_k}}$.In this paper, we present some results on decomposition of Toeplitz graphs.
Samira Hossein Ghorban
doaj +2 more sources
Decompositions of Cubic Traceable Graphs
Discussiones Mathematicae Graph Theory, 2020 A traceable graph is a graph with a Hamilton path. The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular graph and a matching. We prove the conjecture for cubic traceable graphs.
Liu Wenzhong, Li Panpan
doaj +2 more sources
Density-Friendly Graph Decomposition [PDF]
ACM Transactions on Knowledge Discovery from Data, 2019 Decomposing a graph into a hierarchical structure via k -core analysis is a standard operation in any modern graph-mining toolkit. k -core decomposition is a simple and efficient method that allows to analyze a graph beyond its mere degree distribution.
Tatti Nikolaj, Tatti Nikolaj
openaire +3 more sources
Sparsity-certifying Graph Decompositions [PDF]
Graphs and Combinatorics, 2009 We describe a new algorithm, the $(k,\ell)$-pebble game with colors, and use it obtain a characterization of the family of $(k,\ell)$-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances of sparse graphs appear in rigidity theory and have received increased attention in recent years.
Streinu, Ileana, Theran, Louis
openaire +4 more sources
Odd Decompositions of Eulerian Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2017 We prove that an eulerian graph $G$ admits a decomposition into $k$ closed trails of odd length if and only if and it contains at least $k$ pairwise edge-disjoint odd circuits and $k\equiv |E(G)|\pmod{2}$. We conjecture that a connected $2d$-regular graph of odd order with $d\ge 1$ admits a decomposition into $d$ odd closed trails sharing a common ...
Máčajová, Edita, Škoviera, Martin
openaire +2 more sources
α_{2}-labeling of graphs [PDF]
Opuscula Mathematica, 2009 We show that if a graph \(G\) on \(n\) edges allows certain special type of rosy labeling (a.k.a. \(\rho\)-labeling), called \(\alpha_2\)-labeling, then for any positive integer \(k\) the complete graph \(K_{2nk+1}\) can be decomposed into copies of \(G\)
Dalibor Fronček
doaj +1 more source
Note on decompositions based on the vertex-removing synchronised graph product
Electronic Journal of Graph Theory and Applications, 2022 Recently, we have introduced two graph-decomposition theorems based on a new graph product, motivated by applications in the context of synchronising periodic real-time processes. This vertex-removing synchronised product (VRSP) is based on modifications
Antoon Hendrik Boode
doaj +1 more source
TD-H2H: Shortest Path Query on Time-Dependent Graphs [PDF]
Jisuanji kexue yu tansuo, 2023 A shortest path query on road networks is a fundamental problem, which has been studied widely. Existing studies usually model road networks as a static graph and query the path with the shortest distance between given vertices.
LI Xinling, WANG Yishu, YUAN Ye, GU Xiang, WANG Guoren
doaj +1 more source
On the decomposition threshold of a given graph [PDF]
, 2019 We study the $F$-decomposition threshold $\delta_F$ for a given graph $F$. Here an $F$-decomposition of a graph $G$ is a collection of edge-disjoint copies of $F$ in $G$ which together cover every edge of $G$. (Such an $F$-decomposition can only exist if
Glock, Stefan +4 more
core +2 more sources
Decomposition of complete graphs into small graphs [PDF]
Opuscula Mathematica, 2010 In 1967, A. Rosa proved that if a bipartite graph \(G\) with \(n\) edges has an \(\alpha\)-labeling, then for any positive integer \(p\) the complete graph \(K_{2np+1}\) can be cyclically decomposed into copies of \(G\).
Dalibor Froncek
doaj +1 more source