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

• Graph Lineages and Skeletal Graph Products [0.0]
  Graphs, and sequences of growing graphs, can be used to specify the architecture of mathematical models in many fields including machine learning and computational science.<n>We define structured graph "lineages" that grow in a hierarchical fashion, so that the number of graph vertices and edges increases exponentially in level number.<n>We demonstrate such application to deep neural networks (including visual and feature scale spaces) and to multigrid numerical methods.
  arXiv  Detail & Related papers  (2025-07-31T22:31:34Z)
• InstructG2I: Synthesizing Images from Multimodal Attributed Graphs [50.852150521561676]
  We propose a graph context-conditioned diffusion model called InstructG2I. InstructG2I first exploits the graph structure and multimodal information to conduct informative neighbor sampling. A Graph-QFormer encoder adaptively encodes the graph nodes into an auxiliary set of graph prompts to guide the denoising process.
  arXiv  Detail & Related papers  (2024-10-09T17:56:15Z)
• Graphons of Line Graphs [6.822247359790484]
  We show a simple method that can shed light on a subset of sparse graphs. We show that graphs satisfying a particular property, which we call the square-degree property are sparse, but give rise to dense line graphs. In particular, star graphs satisfy the square-degree property resulting in dense line graphs and non-zero graphons of line graphs.
  arXiv  Detail & Related papers  (2024-09-03T06:50:03Z)
• 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)
• A Graph Convolution for Signed Directed Graphs [0.0]
  Graph convolutions for signed directed graphs have not been delivered much yet. We propose a novel complex Hermitian adjacency matrix that encodes graph information via complex numbers. To the best of our knowledge, it is the first spectral convolution for graphs with signs.
  arXiv  Detail & Related papers  (2022-08-23T01:58:35Z)
• 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)
• 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)
• 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)
• Bridging Knowledge Graphs to Generate Scene Graphs [49.69377653925448]
  We propose a novel graph-based neural network that iteratively propagates information between the two graphs, as well as within each of them. Our Graph Bridging Network, GB-Net, successively infers edges and nodes, allowing to simultaneously exploit and refine the rich, heterogeneous structure of the interconnected scene and commonsense graphs.
  arXiv  Detail & Related papers  (2020-01-07T23:35:52Z)

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.