Asymmetric graphs
\(G\) (=ungerichteter, schlingen- und doppelkantenfreier Graph) heißt symmetrisch, wenn es einen nicht-identischen Automorphismus von \(G\) gibt. Verff. führen ein Maß für die Asymmetrie von Graphen ein. Die kleinste Summe \(r+s\), mit der es durch Wegnahme von \(r\) Kanten und Adjunktion von \(s\) (neuen) Kanten gelingt, \(G\) in einen symmetrischen Graphen zu verwandeln, heißt der Asymmetriegrad \(A[G]\) von \(G\). Der Asymmetriegrad des aus einer Ecke bestehenden Graphen wird mit \(+\infty\) festgesetzt. Ferner wird definiert \(A(n) = \text{Max} A[G]\) aller \(G\) mit der (festen) Eckenzahl \(n\). Unter anderem werden folgende Sätze bewiesen: 1. \(A(n) \leq [{1 \over 2} (n-1)]\). 2. Die Wahrscheinlichkeit, unter den \(G\) mit \(n\) Ecken ein \(A[G]/n<{1 \over 2}-\varepsilon\) anzutreffen, konvergiert für jedes (für alle \(n\) gemeinsam gewähltes) \(\varepsilon > 0\) mit \(n \to \infty\) nach 0. 3. \(\lim_{n \to \infty} {A(n) \over n} = {1 \over 2}\) (folgt aus (1) und (2)). 4. Die Wahrscheinlichkeit, unter den abzählbar unendlichen Graphen einen symmetrischen Graphen zu treffen, ist gleich 1. Endliche und abzählbar unendliche Graphen verhalten sich also entgegengesetzt, so daß die meisten endlichen Graphen asymmetrisch (d.h. nicht symmetrisch), die meisten unendlichen Graphen dagegen symmetrisch sind. Von Interesse sind noch mehrere im Text gestellte, offen gebliebene Fragen über den Asymmetriegrad. Zum Beispiel zeigt der Beweis von (1), daß die obere Schranke in (1) auch bei Einschränkung auf diejenigen Automorphismen respektiert wird, bei denen (nur) zwei Ecken in \(G\) vertauscht werden. Ist bei dieser Einschränkung der Automorphismen von \(G\) das Min. von \(r+s\) gleich \({1 \over 2}(n-1)\), so heißt \(G\) ein \(\Delta\)-Graph. Es wird von den Verff. vermutet, daß es keinen Graphen \(G\) gibt mit \(A[G]={1 \over 2} (n-1)\), oder auch stärker, daß alle \(\Delta\)-Graphen symmetrisch sind.
- A Characteristic Property of Quadratic Residues
- Bemerkungen über die Verteilung der quadratischen Reste
- scientific article; zbMATH DE number 3151315 (Why is no real title available?)
- scientific article; zbMATH DE number 3152798 (Why is no real title available?)
- On Chromatic Graphs
- On Sets of Acquaintances and Strangers at any Party
- On the measure of equidistribution of point sets
- Almost all graphs are rigid-revisited
- A surprising permanence of old motivations (a not-so-rigid story)
- The capture time of a graph
- Graph isomorphism problem
- Cyclic automorphisms of a countable graph and random sum-free sets
- Regular orbits of permutation groups on the power set
- The age of a relational structure
- Asymmetrising sets in trees
- Distanced graphs
- Extending partial isomorphisms of graphs
- Minimal asymmetric graphs of induced length 4
- Either tournaments or algebras?
- A note on uniquely reducible graphs
- Cohomological aspects of two-graphs
- Clumps, minimal asymmetric graphs, and involutions
- Homogeneous and ultrahomogeneous linear spaces
- On random relational structures
- Switching with more than two colours.
- Homogeneous Cayley objects
- Kolmogorov random graphs only have trivial stable colorings.
- Detecting almost symmetries of graphs
- Fraïssé limits in comma categories
- A novel approach to perturbative calculations for a large class of interacting boson theories
- The asymmetry number of finite tournaments, and some related results
- Asymptotics of symmetry in matroids
- Low-degree factors of random polynomials
- Some sequences of integers
- On strongly asymmetric graphs
- Enumerating alternating matrix spaces over finite fields with explicit coordinates
- Deciding and verifying network properties locally with few output bits
- Pairings and related symmetry notions
- On graphs whose Wiener complexity equals their order and on Wiener index of asymmetric graphs
- The isomorphism problem of trees from the viewpoint of Terwilliger algebras
- Finite big Ramsey degrees in universal structures
- Copies of the random graph
- Homogeneous actions on the random graph
- Asymptotic enumeration of Cayley digraphs
- Extremal solutions of an inequality concerning supports of permutation groups and punctured Hadamard codes
- Geometric random graphs on circles
- Classical symmetries and the quantum approximate optimization algorithm
- No additional tournaments are quasirandom-forcing
- Ample simplicial complexes
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Community detection with the label propagation algorithm: a survey
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines
- Limited visibility cops and robber
- Almost all trees have quantum symmetry
- Restrained domination in self-complementary graphs
- The Rado simplicial complex
- Distinguishing graphs of maximum valence 3
- Further results on existentially closed graphs arising from block designs
- Vertex nomination: the canonical sampling and the extended spectral nomination schemes
- Bipartite graph embeddings, Riemann surfaces and Galois groups
- The adjacency matrix of a graph as a data table: a geometric perspective
- Topological 2-generation of automorphism groups of countable ultrahomogeneous graphs
- Almost equitable partitions and new necessary conditions for network controllability
- Minimal asymmetric graphs
- Simplicial complexes and closure systems induced by indistinguishability relations
- Statistical graph space analysis
- On the exact maximum induced density of almost all graphs and their inducibility
- Geometric random graphs and Rado sets in sequence spaces
- A calculus for measuring the elegance of abstract graphs
- Random generations of the countable random graph
- An explicit construction of \((3,t)\)-existentially closed graphs
- Graphs with the n-e.c. adjacency property constructed from affine planes
- Fixing subgraphs
- Deeply asymmetric planar graphs
- Undirecting membership in models of anti-foundation
- Infinite quantum permutations
- Distance-regular Cayley graphs over dicyclic groups
- The poset of all copies of the random graph has the 2-localization property
- Controllability of Multi-Agent Dynamical Systems with a Broadcasting Control Signal
- Breaking symmetry in complete graphs by orienting edges: asymptotic bounds
- Generalisations of hypomorphisms and reconstruction of hypergraphs
- Existential closure of block intersection graphs of infinite designs having finite block size and index
- Existential closure of block intersection graphs of infinite designs having infinite block size
- Countable random 𝑝-groups with prescribed Ulm-invariants
- Existentially closed graphs via permutation polynomials over finite fields
- Paley and the Paley Graphs
- Universal homogeneous causal sets
- Almost all graphs are rigid - Revisited
- Graph of a nearring with respect to an ideal.
- Structural Ramsey theory of metric spaces and topological dynamics of isometry groups
- Exploiting symmetries for scaling loopy belief propagation and relational training
- Endomorphism breaking in graphs
- Maximal asymmetry of graphs
- Properties of the automorphism group and a probabilistic construction of a class of countable labeled structures
- Fighting constrained fires in graphs
- Random Permutations: Some Group-Theoretic Aspects
- Most primitive groups are full automorphism groups of edge-transitive hypergraphs.
- Compact navigation and distance oracles for graphs with small treewidth
- Asymmetric and symmetric graphs
- Distinguishing graphs by edge-colourings
- scientific article; zbMATH DE number 2124072 (Why is no real title available?)
- Maximal chains of isomorphic subgraphs of the Rado graph
- Typical automorphism groups of finite nonrigid structures
- Infinite families of asymmetric graphs
- Infinite Paley graphs
- Triply existentially complete triangle-free graphs
This page was built for publication: Asymmetric graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5728982)