Construction numbers: How to build a graph?
- URL: http://arxiv.org/abs/2302.13186v4
- Date: Wed, 19 Jun 2024 22:23:31 GMT
- Title: Construction numbers: How to build a graph?
- Authors: Paul C. Kainen,
- Abstract summary: Counting the number of linear extensions of a partial order was considered by Stanley about 50 years ago.
The number of these c-sequences is counted for various graph families.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Counting the number of linear extensions of a partial order was considered by Stanley about 50 years ago. For the partial order on the vertices and edges of a graph given by inclusion, we call a linear extension a {\it construction sequence} for the graph as each edge follows the vertices where it is attached. The number of these c-sequences is counted for various graph families. We also consider the set of all length-$n$ c-sequences produced by the graphs with $n$ elements, simplified to their structural skeleton: vertex or edge, and further allow the generating graph to be structurally constrained. Efficiency is analyzed.
Related papers
- A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
We introduce GraphsGPT, featuring a Graph2Seq encoder that transforms Non-Euclidean graphs into learnable Graph Words.
A GraphGPT decoder reconstructs the original graph from Graph Words to ensure information equivalence.
arXiv Detail & Related papers (2024-02-04T12:29:40Z) - Finding the Missing-half: Graph Complementary Learning for
Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
Graphs with homophily-prone edges tend to connect nodes with the same class.
Heterophily-prone edges tend to build relationships between nodes with different classes.
Existing GNNs only take the original graph during training.
arXiv Detail & Related papers (2023-06-13T08:06:10Z) - Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
Contrastive learning has emerged as a premier method for learning representations with or without supervision.
Recent studies have shown its utility in graph representation learning for pre-training.
We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
arXiv Detail & Related papers (2023-02-06T16:26:29Z) - Deterministic Graph-Walking Program Mining [10.482805367361818]
We give two algorithms for mining of deterministic graph-walking programs that yield programs in the order of increasing length.
These programs characterise linear long-distance relationships between the given two vertex sets in the context of the whole graph.
arXiv Detail & Related papers (2022-08-22T13:16:13Z) - Explanation Graph Generation via Pre-trained Language Models: An
Empirical Study with Contrastive Learning [84.35102534158621]
We study pre-trained language models that generate explanation graphs in an end-to-end manner.
We propose simple yet effective ways of graph perturbations via node and edge edit operations.
Our methods lead to significant improvements in both structural and semantic accuracy of explanation graphs.
arXiv Detail & Related papers (2022-04-11T00:58:27Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs)
A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data.
We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
arXiv Detail & Related papers (2021-11-12T07:08:13Z) - Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
We present an extensive survey of various exact and inexact graph matching techniques.
A category of graph matching algorithms is presented, which reduces the graph size by removing the less important nodes.
We introduce a novel approach to measure graph similarity using geometric graphs.
arXiv Detail & Related papers (2020-12-30T18:51:06Z) - High-Order Relation Construction and Mining for Graph Matching [36.880853889521845]
Iterated line graphs are introduced for the first time to describe high-order information.
We present a new graph matching method, called High-order Graph Matching Network (HGMN)
By imposing practical constraints, HGMN is made scalable to large-scale graphs.
arXiv Detail & Related papers (2020-10-09T03:30:02Z) - Graph model overview, events scales structure and chains of events [0.0]
We present a graph model for a background independent, relational approach to spacetime.
The graph coloring determines the graph structure in clusters of graph vertices (events) that can be monochromatic (homogeneous loops) or polychromatic (inhomogeneous loops)
The emerging structure has self-similar characteristics on different scales (states)
arXiv Detail & Related papers (2020-07-12T16:42:09Z) - Wasserstein-based Graph Alignment [56.84964475441094]
We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph.
We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
arXiv Detail & Related papers (2020-03-12T22:31:59Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.