skip to main content

Explore Research Products in the NSF-PAR

Title: Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs
An automorphism of a graph is a mapping of the vertices onto themselves such that connections between respective edges are preserved. A vertex v in a graph G is fixed if it is mapped to itself under every automorphism of G. The fixing number of a graph G is the minimum number of vertices, when fixed, fixes all of the vertices in G. The determination of fixing numbers is important as it can be useful in determining the group of automorphisms of a graph-a famous and difficult problem. Fixing numbers were introduced and initially studied by Gibbons and Laison, Erwin and Harary and Boutin. In this paper, we investigate fixing numbers for graphs with an underlying cyclic structure, which provides an inherent presence of symmetry. We first determine fixing numbers for circulant graphs, showing in many cases the fixing number is 2. However, we also show that circulant graphs with twins, which are pairs of vertices with the same neighbourhoods, have considerably higher fixing numbers. This is the first paper that investigates fixing numbers of point-block incidence graphs, which lie at the intersection of graph theory and combinatorial design theory. We also present a surprising result-identifying infinite families of graphs in which fixing any vertex fixes every vertex, thus removing all symmetries from the graph.  more » « less
Award ID(s):
1950189
NSF-PAR ID:
10209860
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
Mathematics
Volume:
9
Issue:
1
ISSN:
2227-7390
Page Range / eLocation ID:
1-16
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ( , Electronic colloquium on computational complexity)
    null (Ed.)
    A graph G is called {\em self-ordered} (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from G to any graph that is isomorphic to G. We say that G=(VE) is {\em robustly self-ordered}if the size of the symmetric difference between E and the edge-set of the graph obtained by permuting V using any permutation :VV is proportional to the number of non-fixed-points of . In this work, we initiate the study of the structure, construction and utility of robustly self-ordered graphs. We show that robustly self-ordered bounded-degree graphs exist (in abundance), and that they can be constructed efficiently, in a strong sense. Specifically, given the index of a vertex in such a graph, it is possible to find all its neighbors in polynomial-time (i.e., in time that is poly-logarithmic in the size of the graph). We provide two very different constructions, in tools and structure. The first, a direct construction, is based on proving a sufficient condition for robust self-ordering, which requires that an auxiliary graph, on {\em pairs} of vertices of the original graph, is expanding. In this case the original graph is (not only robustly self-ordered but) also expanding. The second construction proceeds in three steps: It boosts the mere existence of robustly self-ordered graphs, which provides explicit graphs of sublogarithmic size, to an efficient construction of polynomial-size graphs, and then, repeating it again, to exponential-size(robustly self-ordered) graphs that are locally constructible. This construction can yield robustly self-ordered graphs that are either expanders or highly disconnected, having logarithmic size connected components. We also consider graphs of unbounded degree, seeking correspondingly unbounded robustness parameters. We again demonstrate that such graphs (of linear degree)exist (in abundance), and that they can be constructed efficiently, in a strong sense. This turns out to require very different tools. Specifically, we show that the construction of such graphs reduces to the construction of non-malleable two-source extractors with very weak parameters but with some additional natural features. We actually show two reductions, one simpler than the other but yielding a less efficient construction when combined with the known constructions of extractors. We demonstrate that robustly self-ordered bounded-degree graphs are useful towards obtaining lower bounds on the query complexity of testing graph properties both in the bounded-degree and the dense graph models. Indeed, their robustness offers efficient, local and distance preserving reductions from testing problems on ordered structures (like sequences) to the unordered (effectively unlabeled) graphs. One of the results that we obtain, via such a reduction, is a subexponential separation between the query complexities of testing and tolerant testing of graph properties in the bounded-degree graph model. Changes to previous version: We retract the claims made in our initial posting regarding the construction of non-malleable two-source extractors (which are quasi-orthogonal) as well as the claims about the construction of relocation-detecting codes (see Theorems 1.5 and 1.6 in the original version). The source of trouble is a fundamental flaw in the proof of Lemma 9.7 (in the original version), which may as well be wrong. Hence, the original Section 9 was omitted, except that the original Section 9.3 was retained as a new Section 8.3. The original Section 8 appears as Section 8.0 and 8.1, and Section 8.2 is new. 
    more » « less
  2. ; ; ( , Journal of Graph Theory)
    Abstract

    Letbe integers with, and set. Erdős proved that when, eachn‐vertex nonhamiltonian graphGwith minimum degreehas at mostedges. He also provides a sharpness examplefor all such pairs. Previously, we showed a stability version of this result: fornlarge enough, every nonhamiltonian graphGonnvertices withand more thanedges is a subgraph of. In this article, we show that not only does the graphmaximize the number of edges among nonhamiltonian graphs withnvertices and minimum degree at leastd, but in fact it maximizes the number of copies of any fixed graphFwhennis sufficiently large in comparison withdand. We also show a stronger stability theorem, that is, we classify all nonhamiltoniann‐vertex graphs withand more thanedges. We show this by proving a more general theorem: we describe all such graphs with more thancopies offor anyk.

     
    more » « less
  3. ; ; ; ( , Communications of the American Mathematical Society)
    Given any graph G G , the spread of G G is the maximum difference between any two eigenvalues of the adjacency matrix of G G . In this paper, we resolve a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs. The first states that for all positive integers n n , the n n -vertex graph G G that maximizes spread is the join of a clique and an independent set, with ⌊ 2 n / 3 ⌋ \lfloor 2n/3 \rfloor and ⌈ n / 3 ⌉ \lceil n/3 \rceil vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all n n sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over L 2 [ 0 , 1 ] \mathscr {L}^2[0,1] . The second conjecture claims that for any fixed m ≤ n 2 / 4 m \leq n^2/4 , if G G maximizes spread over all n n -vertex graphs with m m edges, then G G is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we construct an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower-order error terms. 
    more » « less
  4. ; ; ; ; ( , Journal of Graph Theory)
    Abstract

    A graph is ‐freeif it has no induced subgraph isomorphic to , and |G| denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that:

    For every graph , there exists such that in every ‐free graph with |G| there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.

    This is equivalent to:

    The “sparse linear conjecture”: For every graph , there exists such that in every ‐free graph with , either some vertex has degree at least , or there are two disjoint sets of vertices, of sizes at least and , anticomplete to each other.

    We prove a number of partial results toward the sparse linear conjecture. In particular, we prove it holds for a large class of graphs , and we prove that something like it holds for all graphs . More exactly, say is “almost‐bipartite” if is triangle‐free and can be partitioned into a stable set and a set inducing a graph of maximum degree at most one. (This includes all graphs that arise from another graph by subdividing every edge at least once.) Our main result is:

    The sparse linear conjecture holds for all almost‐bipartite graphs .

    (It remains open when is the triangle .) There is also a stronger theorem:

    For every almost‐bipartite graph , there exist such that for every graph with and maximum degree less than , and for every with , either contains induced copies of , or there are two disjoint sets with and , and with at most edges between them.

    We also prove some variations on the sparse linear conjecture, such as:

    For every graph , there exists such that in every ‐free graph with vertices, either some vertex has degree at least , or there are two disjoint sets of vertices with , anticomplete to each other.

     
    more » « less
  5. ; ; ; ; ; ( , Journal of Graph Theory)
    Abstract

    Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph begin in one of two states, “dormant” or “active.” Given a fixed positive integer , a dormant vertex becomes active if at any stage it has at least active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices , we say thatG‐percolates (from ) if every vertex in becomes active after some number of steps. Let denote the minimum size of a set such thatG‐percolates from . Bootstrap percolation has been studied in a number of settings and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree‐based density conditions that ensure . In particular, we give an Ore‐type degree sum result that states that if a graph satisfies , then either or is in one of a small number of classes of exceptional graphs. (Here, is the minimum sum of degrees of two nonadjacent vertices in .) We also give a Chvátal‐type degree condition: If is a graph with degree sequence such that or for all , then or falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore‐type result in a paper by Freund et al.

     
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email