2-distance Zero Forcing Sets in Graphs Hassan, Javier; Udtohan, Lestlene T.; Laja, Ladznar S.
European journal of pure and applied mathematics,
04/2024, Volume:
17, Issue:
2
Journal Article
Peer reviewed
Open access
In this paper, we introduce new concept in graph theory called 2-distance zero forcing. We give some properties of this new parameter and investigate its connections with other parameters such as ...zero forcing and hop domination. We show that 2-distance zero forcing and hop domination (respectively, zero forcing parameter) are incomparable. Moreover, we characterize 2-distance zero forcing sets in some special graphs, and finally derive the exact values or bounds of the parameter using these results.
This paper begins the study of reconfiguration of zero forcing sets, and more specifically, the zero forcing graph. Given a base graph G, its zero forcing graph, Z(G), is the graph whose vertices are ...the minimum zero forcing sets of G with an edge between vertices B and B′ of Z(G) if and only if B can be obtained from B′ by changing a single vertex of G. It is shown that the zero forcing graph of a forest is connected, but that many zero forcing graphs are disconnected. We characterize the base graphs whose zero forcing graphs are complete graphs, and show that the star cannot be a zero forcing graph. We show that computing Z(G) takes 2Θ(n) operations in the worst case for a graph G of order n.
In this paper, we initiate the study of a zero forcing hop domination in a graph. We establish some properties of this parameter and we determine its connections with other known parameters in graph ...theory. Moreover, we obtain some exact values or bounds of the parameter on the generalized graph, some families of graphs, and graphs under some operations via characterizations.
Zero forcing with random sets Curtis, Bryan; Gan, Luyining; Haddock, Jamie ...
Discrete mathematics,
20/May , Volume:
347, Issue:
5
Journal Article
Peer reviewed
Given a graph G and a real number 0≤p≤1, we define the random set Bp(G)⊆V(G) by including each vertex independently and with probability p. We investigate the probability that the random set Bp(G) is ...a zero forcing set of G. In particular, we prove that for large n, this probability for trees is upper bounded by the corresponding probability for a path graph. Given a minimum degree condition, we also prove a conjecture of Boyer et al. regarding the number of zero forcing sets of a given size that a graph can have.
A subset Z of vertex set V(G) of a graph G is a zero forcing set of G if iteratively adding vertices to Z from V(G)∖Z that are the unique neighbor in V(G)∖Z of some vertex in Z, results in the entire ...V(G) of G. The zero forcing number Z(G) of G is the minimum cardinality of a zero forcing set of G. In a recent work, Caro and Pepper (2015) proved that Z(G)≤(Δ−2)n−(Δ−δ)+2Δ−1, where n,Δ,δ are the order, maximum degree, minimum degree of G, respectively. In this paper we completely characterize extremal graphs attained the upper bound, solving a problem proposed by Lu et al. (2016). Our result further generalizes the characterization of extremal regular graphs obtained by Gentner et al. and Lu et al. in 2016.
Characterization of network controllability through its topology has recently gained a lot of attention in the systems and control community. Using the notion of balancing sets, in this note, such a ...network-centric approach for the controllability of certain families of undirected networks is investigated. Moreover, by introducing the notion of a generalized zero forcing set, the structural controllability of undirected networks is discussed; in this direction, lower bounds on the dimension of the controllable subspace are derived. In addition, a method is proposed that facilitates synthesis of structural and strong structural controllable networks as well as examining preservation of network controllability under structural perturbations.
Zero forcing number of a graph is the minimum cardinality of the zero forcing set. A zero forcing set is a set of black vertices of minimum cardinality that can colour the entire graph black using ...the color change rule: each vertex of G is coloured either white or black, and vertex v is a black vertex and can force a white neighbour only if it has one white neighbour. In this paper we identify a class of graph where the zero forcing number is equal to the minimum rank of the graph and call it as a new class of graph that is open global shadow graph”. Some of the basic properties of open global shadow graph are studied. The zero forcing number of open global shadow graph of a graph with upper and lower bound is obtained. Hence giving the upper and lower bound for the minimum rank of the graph.
We consider the uplink of a multicell multiuser single-input multiple-output system (MU-SIMO), where the channel experiences both small- and large-scale fading. The data detection is done by using ...the linear zero-forcing technique, assuming the base station (BS) has perfect channel state information of all users in its cell. We derive new exact analytical expressions for the uplink rate, the symbol error rate (SER), and the outage probability per user, as well as a lower bound on the achievable rate. This bound is very tight and becomes exact in the large-number-of-antenna limit. We further study the asymptotic system performance in the regimes of high signal-to-noise ratio (SNR), large number of antennas, and large number of users per cell. We show that, at high SNRs, the system is interference limited, and hence, we cannot improve the system performance by increasing the transmit power of each user. Instead, by increasing the number of BS antennas, the effects of interference and noise can be reduced, thereby improving system performance. We demonstrate that, with very large antenna arrays at the BS, the transmit power of each user can be made inversely proportional to the number of BS antennas while maintaining a desired quality of service. Numerical results are presented to verify our analysis.
Zero forcing is a combinatorial game played on a graph with the ultimate goal of changing the colour of all the vertices at minimal cost. Originally this game was conceived as a one player game, but ...later a two-player version was devised in-conjunction with studies on the inertia of a graph, and has become known as the q-analogue of zero forcing. In this paper, we study and compute the q-analogue zero forcing number for various families of graphs. We begin with by considering a concept of contraction associated with trees. We then significantly generalize an equation between this q-analogue of zero forcing and a corresponding nullity parameter for all threshold graphs. We close by studying the q-analogue of zero forcing for certain Kneser graphs, and a variety of cartesian products of structured graphs.
PDF