Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Darren A. Narayan has a total of 62 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Asymptotics of Closeness Centralities of Graphs

    by Santiago Frias, Adriana Galindo Silva, Bryan Romero, Darren A. Narayan

    Given a connected graph G with n vertices, the distance between two vertices is the number of edges in a shortest path connecting them. The sum of the distances in a graph G from a vertex v to all other vertices is denoted by SDG(v). The closeness centrality of a vertex in a graph was defined by Bavelas to be CC(v)=n−1SDG(v) and the closeness centrality of G is CC(G)=∑v∈Gn−1SDG(v). We consider the asymptotic limit of CC(G) as the number of vertices tends to infinity and provide an elegant and insightful proof of a 2025 result by Britz, Hu, Islam, and Tang, limn→∞CC(Pn)=π, using uniform convergence and Riemann sums. We applied the same technique for the union of a cycle Cm and path Pn and the union of a path and a complete graph. We prove that of all graphs, paths have the minimum closeness centrality. Next we show for any c∈[π,∞), there exists a sequence of graphs {Gn} such that limn→∞CC(Gn)=c. In addition, we investigate the mean distance of a graph, l¯(G)=1n(n−1)∑v∈V(G)SD(v) and the normalized closeness centrality, C¯C(G)=1nCC(G). We verify a conjecture of Britz, Hu, Islam, and Tang that the set of products {l¯(G)C¯C(G):Gisfiniteandconnected} is dense in [1,2).


  • Open Access

    Maximal bipartite graphs with a unique minimum dominating set

    by Garrison Koch, Darren Narayan

    In 2003, Fischermann et al. considered the maximum size of \textit{uniquely-dominatable} graphs, graphs whose dominating number is realized only by a unique dominating set. They conjectured a size bound and provide a general graph construction that shows the bound is tight \cite{Original_Paper}. In 2010, Shank and Fraboni prove Fischermann's bound is true when $γ= 2$ \cite{Shank_paper}. In this paper, we observe how Fischermann's bound changes if we impart a different restriction on a graph -- bipartiteness. We conjecture a bound on the maximum number of edges possible for uniquely-dominatable bipartite graphs. We provide constructions to demonstrate this bound is tight. We prove our bipartite bound is true for the $γ= 2$ and $n = 3γ$ cases. We also discuss perfect domination and how it relates to our extremal graph constructions. We provide constructions that meet both Fischermann's bound for all graphs and our bound for bipartite graphs respectively, both of which are perfectly dominated.

  • Open Access

    The asymmetric index of a graph

    by Darren Narayan, Alejandra Brewer, Adam Gregory, Quindel Jones, Natalie Gomez, Emma Farnsworth, Brendan Rooney, Herlandt Lino

    A graph $G$ is asymmetric if its automorphism group is trivial. Asymmetric graphs were introduced by Erdős and Rényi (1963). They suggested the problem of starting with an asymmetric graph and removing some number $r$ of edges and/or adding some number $s$ of edges so that the resulting graph is nonasymmetric. Erdős and Rényi defined the degree of asymmetry of a graph to be the minimum value of $r+s$. In this paper, we define another property that measures how close a given nonasymmetric graph is to being asymmetric. We define the asymmetric index of a graph $G$, denoted $ai(G)$, to be the minimum of $r+s$ so that the resulting graph $G$ is asymmetric. We investigate the asymmetric index of both connected and disconnected graphs. We prove that for any nonnegative integer $k$, there exists a graph $G$ where $ai(G)=k$. We show that the asymmetric index of a cycle with at least six vertices is two, and provide a complete characterization of all possible pairs of edges that can be added to a cycle to create an asymmetric graph. In addition we determine the asymmetric index of paths, certain circulant graphs, Cartesian products involving paths and cycles, and bounds for complete graphs, and complete bipartite graphs.

  • Open Access

    Failed Skew Zero Forcing Numbers of Path Powers and Circulant Graphs

    by Aidan Johnson, Andrew Vick, Rigoberto Flórez, Darren A. Narayan

    For a graph G, the zero forcing number of G, Z(G), is defined to be the minimum cardinality of a set S of vertices for which repeated applications of the forcing rule results in all vertices being in S. The forcing rule is as follows: if a vertex v is in S, and exactly one neighbor u of v is not in S, then the vertex u is added to S in the subsequent iteration. Now, the failed zero forcing number of a graph is defined to be the maximum size of a set of vertices which does not force all of the vertices in the graph. A similar type of forcing is called skew zero forcing, which is defined so that if there is exactly one neighbor u of v that is not in S, then the vertex u is added to S in the next iteration. The key difference is that vertices that are not in S can force other vertices. The failed skew zero forcing number of a graph is denoted by F−(G). At its core, the problem we consider is how to identify the tipping point at which information or infection will spread through a network or a population. The graphs we consider are where computers/routers or people are arranged in a linear or circular formation with varying proximities for contagion. Here, we present new results for failed skew zero forcing numbers of path powers and circulant graphs. Furthermore, we found that the failed skew zero forcing numbers of these families form interesting sequences with increasing n.

  • Open Access

    Closeness Centrality of Asymmetric Trees and Triangular Numbers

    by Nytha Ramanathan, Eduardo Ramirez, Dorothy Suzuki-Burke, Darren A. Narayan

    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.


  • Open Access

    Failed Zero Forcing Numbers of Trees and Circulant Graphs

    by University of Arkansas, Luis Gomez, Karla Rubi, California State University- Dominguez Hills, Jordan Terrazas, Southern Methodist University, Rigoberto Florez, The Citadel, Darren Narayan, Rochester Institute of Technology

    Given a graph $G$, the zero forcing number of $G$, $Z(G)$, is the smallest cardinality of any set $S$ of vertices on which repeated applications of the forcing rule (described below) results in all vertices being in $S$. The forcing rule is as follows: if a vertex $v$ is in $S$, and exactly one neighbor $u$ of $v$ is not in $S$, then $u$ is added to $S$ in the next iteration. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by $G$. In this paper we investigate the largest size of a set $S$ that does not force all of the vertices in a graph to be in $S$. This property is known as the failed zero forcing number of a graph and will be denoted by $F(G)$. This property has been investigated in recent years, including a proof by Shitov that the determination of $F(G)$ is NP-complete. In this paper we present new results involving $F(G)$ for trees including a lower bound based on the independence number. In addition we develop new extremal methods and use them determine $F(G)$ for families of circulant graphs.


  • Open Access

    An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of k

    by Chirag Kaudan, Rachel Taylor, Darren A. Narayan

    For a given a graph G, the zero forcing number of G, Z(G), is the smallest cardinality of any set S of vertices on which repeated applications of the forcing rule results in all vertices being included in S. The forcing rule is as follows: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. The failed zero forcing number of a graph was introduced by Fetcie, Jacob, and Saavedra and was defined as the cardinality of the largest set of vertices which fails to force all vertices in the graph. In 2021, Gomez et al. proved that there were exactly 15 graphs with a failed zero forcing number of two, but their proof was complicated, requiring the analysis of many graph families. We present an “inverse” approach where we start with a set of vertices S and then see which graphs have S as a maximum-sized failed zero forcing set. This results in not only a shorter proof but characterizes which graphs have a particular failed zero forcing set. In our proof, we characterize the graphs which have a failed zero forcing set S where |S|=2, meaning considering all simple graphs of order two as induced subgraphs. This approach also has greater potential for characterizing graphs where F(G)>2 since many general arguments on the structure of graphs are developed in this type of analysis and are applicable for failed zero forcing sets of any size.


  • Open Access

    Fixing Numbers of Point-Block Incidence Graphs

    by Josephine Brooks, Alvaro Carbonero, Joseph Vargas, Rigoberto Flórez, Brendan Rooney, Darren A. Narayan

    A vertex in a graph is referred to as fixed if it is mapped to itself under every automorphism of the vertices. The fixing number of a graph is the minimum number of vertices, when fixed, that fixes all of the vertices in the graph. Fixing numbers were first introduced by Laison and Gibbons, and independently by Erwin and Harary. Fixing numbers have also been referred to as determining numbers by Boutin. The main motivation is to remove all symmetries from a graph. A very simple application is in the creation of QR codes where the symbols must be fixed against any rotation. We determine the fixing number for several families of graphs, including those arising from combinatorial block designs. We also present several infinite families of graphs with an even stronger condition, where fixing any vertex in a graph fixes every vertex.

  • Open Access

    Characterization of All Graphs with a Failed Skew Zero Forcing Number of 1

    by Aidan Johnson, Andrew E. Vick, Darren A. Narayan

    Given a graph G, the zero forcing number of G, Z(G), is the minimum cardinality of any set S of vertices of which repeated applications of the forcing rule results in all vertices being in S. The forcing rule is: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. Hence the failed zero forcing number of a graph was defined to be the cardinality of the largest set of vertices which fails to force all vertices in the graph. A similar property called skew zero forcing was defined so that if there is exactly one neighbor u of v is not in S, then u is added to S in the next iteration. The difference is that vertices that are not in S can force other vertices. This leads to the failed skew zero forcing number of a graph, which is denoted by F−(G). In this paper, we provide a complete characterization of all graphs with F−(G)=1. Fetcie, Jacob, and Saavedra showed that the only graphs with a failed zero forcing number of 1 are either: the union of two isolated vertices; P3; K3; or K4. In this paper, we provide a surprising result: changing the forcing rule to a skew-forcing rule results in an infinite number of graphs with F−(G)=1.


  • Open Access

    All Graphs with a Failed Zero Forcing Number of Two

    by Luis Gomez, Karla Rubi, Jorden Terrazas, Darren A. Narayan

    Given a graph G, the zero forcing number of G, Z(G), is the smallest cardinality of any set S of vertices on which repeated applications of the forcing rule results in all vertices being in S. The forcing rule is: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. In this paper, we investigate the largest size of a set S that does not force all of the vertices in a graph to be in S. This quantity is known as the failed zero forcing number of a graph and will be denoted by F(G). We present new results involving this parameter. In particular, we completely characterize all graphs G where F(G)=2, solving a problem posed in 2015 by Fetcie, Jacob, and Saavedra.