Results 21 to 30 of about 2,245,805 (347)
The monadic second-order logic of graphs XVI : Canonical graph decompositions [PDF]
Logical Methods in Computer Science, 2006 This article establishes that the split decomposition of graphs introduced by Cunnigham, is definable in Monadic Second-Order Logic.This result is actually an instance of a more general result covering canonical graph decompositions like the modular ...
Bruno Courcelle
doaj +1 more source
LightGCL: Simple Yet Effective Graph Contrastive Learning for Recommendation [PDF]
International Conference on Learning Representations, 2023 Graph neural network (GNN) is a powerful learning approach for graph-based recommender systems. Recently, GNNs integrated with contrastive learning have shown superior performance in recommendation with their data augmentation schemes, aiming at dealing ...
Xuheng Cai +3 more
semanticscholar +1 more source
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
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
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
Decomposition of product graphs into paths and stars on five vertices
AKCE International Journal of Graphs and Combinatorics, 2020 Let Sk and Kk respectively denote a path, a star and a complete graph on k vertices. By a -decomposition of a graph G, we mean a decomposition of G into r copies of and s copies of In this paper, it shown that the graph admits a -decomposition if and ...
M. Ilayaraja +2 more
doaj +1 more source
α_{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
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
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
Some results on Steiner decomposition number of graphs
Kuwait Journal of Science, 2023 Let $G$ be a connected graph with Steiner number $s(G)$. A decomposition $\pi=\{G_1, G_2,..., G_n\}$ is said to be a Steiner decomposition if $s(G_i)=s(G)$ for all $i\:(1\leq i\leq n)$. The maximum cardinality obtained for the Steiner decomposition $\pi$
E.Ebin Raja Merly, M.Mahiba
doaj +1 more source