On the diameters of friends-and-strangers graphs

DOI10.5070/C64264229zbMATH Open1547.05073MaRDI QIDQ6615519FDOQ6615519

Authors: Ryan Jeong 

Publication date: 8 October 2024

Published in: Combinatorial Theory (Search for Journal in Brave)

Recommendations

• Friends and strangers walking on graphs
• On the asymmetric generalizations of two extremal questions on friends-and-strangers graphs
• Typical and extremal aspects of friends-and-strangers graphs
• Friends and strangers walking on graphs

zbMATH Keywords

pathslower boundsdiameterextremal combinatoricscyclesinterchange processtoken swappingfriends-and-strangers graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A group-theoretic model for symmetric interconnection networks
• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• A strong uniform time for random transpositions
• A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
• Acyclic orientations of random graphs
• An equivalence relation on the symmetric group and multiplicity-free flag \(h\)-vectors
• Approximation and hardness of token swapping
• Combinatorial and computational aspects of graph packing and graph decomposition
• Complexity of token swapping and its variants
• Compositions of random transpositions
• Connectedness of friends-and-strangers graphs of complete bipartite graphs and others
• Connectivity of friends-and-strangers graphs on random pairs
• Connectivity of old and new models of friends-and-strangers graphs
• Edge disjoint placement of graphs
• Elements of a theory of computer simulation. I
• Friends and strangers walking on graphs
• Friends and strangers walking on graphs
• Generating a random permutation with random transpositions
• Graph puzzles, homotopy, and the alternating group
• Mixing times for the interchange process
• Mixing times of lozenge tiling and card shuffling Markov chains
• Non-separable and planar graphs.
• On reorienting graphs by pushing down maximal vertices
• On the asymmetric generalizations of two extremal questions on friends-and-strangers graphs
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Packing of graphs - a survey
• Packing random graphs and hypergraphs
• Packings of graphs and applications to computational complexity
• Posets from admissible Coxeter sequences.
• Powers of Coxeter elements in infinite groups are reduced
• Proof of Aldous' spectral gap conjecture
• Reversible computation using swap reactions on a surface
• Sharp phase transition in the random stirring model on trees
• Shuffling Cards and Stopping Times
• Sliding puzzles and rotating puzzles on graphs
• Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves
• Sorting on graphs by adjacent swaps using permutation groups
• Swapping labeled tokens on graphs
• The Graph of Linear Extensions Revisited
• The complexity of finding minimum-length generator sequences
• The interchange process on high-dimensional products
• The minimum degree threshold for perfect graph packings
• The probability of long cycles in interchange processes
• The time complexity of permutation routing via matching, token swapping and a variant
• Token Swapping on Trees
• Toric partial orders
• Typical and extremal aspects of friends-and-strangers graphs
• Whitney numbers of the second kind for the star poset

This page was built for publication: On the diameters of friends-and-strangers graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6615519)