More Like this

1. On Weak Flexibility in Planar Graphs

   https://doi.org/10.1007/s00373-022-02564-1  

   Lidický, Bernard; Masařík, Tomáš; Murphy, Kyle; Zerbib, Shira (December 2022, Graphs and Combinatorics)

   Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable. 

   more » « less
2. Finding Cliques in Social Networks: A New Distribution-Free Model

   Fox, James; Roughgarden, Tim; Seshadhri, C; Wei, Fan and (July 2018, SIAM journal on computing)

   This paper proposes a new distribution-free model of social networks. The definitions are motivated by one of the most universal signatures of social networks, triadic closure—the property that pairs of vertices with common neighbors tend to be adjacent. Our most basic definition is that of a c-closed graph, where for every pair of vertices u, v with at least c common neighbors, u and v are adjacent. We study the classic problem of enumerating all maximal cliques, an important task in social network analysis. We prove that this problem is fixed-parameter tractable with respect to c on c-closed graphs. Our results carry over to weakly c-closed graphs, which only require a vertex deletion ordering that avoids pairs of non-adjacent vertices with c common neighbors. Numerical experiments show that well-studied social networks with thousands of vertices tend to be weakly c-closed for modest values of c. 

   more » « less
3. Planar Lattice Subsets with Minimal Vertex Boundary

   https://doi.org/10.37236/10055  

   Gupta, Radhika; Levcovitz, Ivan; Margolis, Alexander; Stark, Emily (July 2021, The Electronic Journal of Combinatorics)

   A subset of vertices of a graph is minimal if, within all subsets of the same size, its vertex boundary is minimal. We give a complete, geometric characterization of minimal sets for the planar integer lattice $$X$$. Our characterization elucidates the structure of all minimal sets, and we are able to use it to obtain several applications. We show that the neighborhood of a minimal set is minimal. We characterize uniquely minimal sets of $$X$$: those which are congruent to any other minimal set of the same size. We also classify all efficient sets of $$X$$: those that have maximal size amongst all such sets with a fixed vertex boundary. We define and investigate the graph $$G$$ of minimal sets whose vertices are congruence classes of minimal sets of $$X$$ and whose edges connect vertices which can be represented by minimal sets that differ by exactly one vertex. We prove that G has exactly one infinite component, has infinitely many isolated vertices and has bounded components of arbitrarily large size. Finally, we show that all minimal sets, except one, are connected. 

   more » « less
4. Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs

   https://doi.org/10.3390/math9020166  

   Brooks, Josephine; Carbonero, Alvaro; Vargas, Joseph; Florez, Rigoberto; Rooney, Brendan; Narayan, Darren A (January 2021, Mathematics)

   null (Ed.)

   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
5. Closeness Centrality of Asymmetric Trees and Triangular Numbers

   https://doi.org/10.3390/math12192994  

   Ramanathan, Nytha; Ramirez, Eduardo; Suzuki-Burke, Dorothy; Narayan, Darren A (October 2024, Mathematics)

   The combinatorial problem in this paper is motivated by a variant of the famous traveling salesman problem where the salesman must return to the starting point after each delivery. The total length of a delivery route is related to a metric known as closeness centrality. The closeness centrality of a vertex v in a graph G was defined in 1950 by Bavelas to be CC(v)=|V(G)|−1SD(v), where SD(v) is the sum of the distances from v to each of the other vertices (which is one-half of the total distance in the delivery route). We provide a real-world example involving the Metro Atlanta Rapid Transit Authority rail network and identify stations whose SD values are nearly identical, meaning they have a similar proximity to other stations in the network. We then consider theoretical aspects involving asymmetric trees. For integer values of k, we considered the asymmetric tree with paths of lengths k,2k,…,nk that are incident to a center vertex. We investigated trees with different values of k, and for k=1 and k=2, we established necessary and sufficient conditions for the existence of two vertices with identical SD values, which has a surprising connection to the triangular numbers. Additionally, we investigated asymmetric trees with paths incident to two vertices and found a sufficient condition for vertices to have equal SD values. This leads to new combinatorial proofs of identities arising from Pascal’s triangle. 

   more » « less