Search

Given a set system (also well-known as a hypergraph) H = {U, X}, where U is a set of elements and X is a set of subsets of U, an exact hitting set S is a subset of U such that each subset in X contains exactly one element in S. We refer to a set system as exactly hittable if it has an exact hitting set. In this paper, we study interval graphs which have intersection models that are exactly hittable. We refer to these interval graphs as Exactly Hittable Interval Graphs (EHIG). We present a forbidden structure characterization for EHIG. We also show that the class of proper interval graphs is a strict subclass of EHIG. Finally, we give an algorithm that runs in polynomial time to recognize graphs belonging to the class of EHIG. [ABSTRACT FROM AUTHOR]

The index ≥1(1) of a signed graph 1= (G; -) is just the largest eigenvalue of its adjacency matrix. For any n > 4 we identify the signed graphs achieving the minimum index in the class of signed bicyclic graphs with n vertices. Apart from the n = 4 case, such graphs are obtained by considering a starlike tree with four branches of suitable length (i.e. four distinct paths joined at their end vertex u) with two additional negative independent edges pairwise joining the four vertices adjacent to u. As a by-product, all signed bicyclic graphs containing a theta-graph and whose index is less than 2 are detected. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V (G). A double Italian dominating function (DIDF) is a function f: V (G) having the property that f(N[u]) 3 for every vertex u 2 V (G) with f(u) 2 f0; 1g, where N[u] is the closed neighborhood of u. If f is a DIDF on G, then let V0 = fv 2 V (G): f(v) = 0g. A restrained double Ital-ian dominating function (RDIDF) is a double Italian dominating function f having the property that the subgraph induced by V0 does not have an isolated vertex. The weight of an RDIDF f is the sum P v2V (G) f(v), and the minimum weight of an RDIDF on a graph G is the restrained double Italian domination number. We present bounds and Nordhaus-Gaddum type results for the restrained double Italian domination number. In addition, we determine the restrained double Italian domination number for some families of graphs. [ABSTRACT FROM AUTHOR]

Topological indices are graph invariants computed usually by means of the distances or degrees of vertices of a graph. In chemical graph theory, a molecule can be modeled by a graph by replacing atoms by the vertices and bonds by the edges of this graph. Topological graph indices have been successfully used in determining the structural properties and in predicting certain physicochemical properties of chemical compounds. Wiener index is the oldest topological index which can be used for analyzing intrinsic properties of a molecular structure in chemistry. The Wiener index of a graph G is equal to the sum of distances between all pairs of vertices of G. Recently, the entire versions of several indices have been introduced and studied due to their applications. Here we introduce the entire Wiener index of a graph. Exact values of this index for trees and some graph families are obtained, some properties and bounds for the entire Wiener index are established. Exact values of this new index for subdivision and k-subdivision graphs and some graph operations are obtained. [ABSTRACT FROM AUTHOR]

Graph theory is the one of the most important concepts which takes the great roll in the electronic devices IC's. These components are known as chips and include complicated, layered microcircuits that can be described by lines or arcs as sets of points. By utilizing graph theory, mathematicians create integrated chips with maximum part density and minimum total interconnecting conductor length. [ABSTRACT FROM AUTHOR]

This paper obtains Reciprocal Complementary Wiener Index of the molecular graph of Naphthalene byusing Minimum Dominating Distance Matrix. [ABSTRACT FROM AUTHOR]

In this paper, we focus on one type of labeling is called co-efficient of range labeling, we have introduced co-efficient of range labeling for Double star graph, Star trees, Spider Trees and Symmetrical Trees. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a graph. A subset D of the vertex set V(G) of a graph G is a strong co-secure dominating set if every vertex v ∈ V - D there exists u ∈ D such that uv ∈ E(G) then D\{u} ∪ {v} and deg(u) ≥ deg(v). The strong co-secure domination number is the minimum cardinality of a strong co-secure dominating set of G, and it is denoted by yscsd (G). The strong co-secure dominating set of G is found for path, cycle, helm graph, closed helm graph, Petersen graph, gear graph, Tadpole graph, and Butterfly graph. [ABSTRACT FROM AUTHOR]

An equitable edge coloring of a graph is a proper edge coloring for which the difference between any two color classes is at most one. The minimum cardinality of G for such coloring is called equitable edge chromatic number. In this article, we determine the theorem on equitable edge coloring for Gear graph Gn, Double star graph K1, n, n and Fan graph F1, n respectively. [ABSTRACT FROM AUTHOR]

A set is a neighbourhood total restrained dominating set of a graph if all the vertices in has one or more adjacent vertex in as well as in and also the each vertex in is adjacent to at least a vertex in and if the induced sub-graph has no isolated vertex. The cardinality of a minimum total restrained dominating set is called total restrained dominating number and is represented as. In this paper, we are introducing Neighborhood total restrained domination and develop an algorithm to find neighbourhood total restrained dominating set for Interval graphs and circular-arc graphs. [ABSTRACT FROM AUTHOR]

The goal of this article provides the common formula for Minimal Domination Cardinality for all Hamiltonian Path or Hamiltonian Circuit. It is explained the way of structures and characteristics of General Hamiltonian Path or Hamiltonian Circuit. It invents the result that all the Hamiltonian Circuit from the given graph should be Cycle Graph. These derived formulae are common for all graphs those have Hamiltonian path or Hamiltonian Circuit. This formula is used to find Maximal Dominating Cardinality in a simple manner. Even though complicated graph also which has Hamiltonian Circuit is evaluating the Cardinality of Maximal Dominating Set is very easy way. [ABSTRACT FROM AUTHOR]

Rosa [11] introduced the notion of graceful labelings. The concept of magic, antimagic and conservative labelings have been extended to directed graphs [9]. Bloom and Hsu [3,4,5] extended the notion of graceful labeling to directed graph. In 1985, Lo [10] introduced the notion of edge-graceful graphs. We introduced the concept of edge-graceful labelings to directed graphs and further studied in [15,16,17,18,19,20]. In this paper we investigate directed edge-graceful labeling of one point union of m-copies of path graph. [ABSTRACT FROM AUTHOR]

The F-average eccentric graph AEF (G) of a graph G has the vertex set as in G and any two vertices u and V are adjacent in AEF (G) if either they are at a distance... different components while G is disconnected. A graph G is called a F -average eccentric graph if AEF (H) ≅ G for some graph H. The main aim of this paper is to find a necessary and sufficient condition for a graph to be a F-average eccentric graph. [ABSTRACT FROM AUTHOR]

In this paper all graphs are finite natural numbers, simple and undirected. A graph labelling is assigned by an integer to the vertices. Here we have discussed some theoretical investigation and found the graphical partitions of triangular number graph, thereafter focused on an algorithm and forwarded an application relating to our theoretical investigation. [ABSTRACT FROM AUTHOR]

The application of graph theory in simulating the key characteristics of systems with finite components has been welldocumented. The telephone network, the train network, communication issues, the traffic network, and many other networks are shown graphically. Graph theoretic models can occasionally provide a helpful structure for the application of analytic methods. Modeling a relationship between a group of things using a graph is another option. An edge represents the relationship between two items if they have an unordered relationship, whereas a directed edge represents the relationship between two ordered objects. [ABSTRACT FROM AUTHOR]

A set S ⊆ V(G) in a graph G is said to be a [1,2]-complementary connected dominating set, if for every vertex 𝑣 ∈ V - S, 1 ≤ |𝑁(𝑣) ∩ S| ≤ 2 and < V - S > is connected. The minimum cardinality of a [1,2]-complementary connected dominating set is called the [1,2]-complementary connected domination number and is denoted by 𝛾[1,2]𝑐𝑐 (G). In this paper, we exhibited the results based on [1,2]-complementary connected domination number for total graph. [ABSTRACT FROM AUTHOR]

In the d-dimensional hypercube bin packing problem, a given list of d-dimensional hypercubes must be packed into the smallest number of hypercube bins. Epstein and van Stee [SIAM J. Comput. 35 (2005)] showed that the asymptotic performance ratio ρ of the online bounded space variant is Ω(log d) and O(d/ log d), and conjectured that it is Θ(log d). We show that ρ is in fact Θ(d/ log d), using probabilistic arguments. [ABSTRACT FROM AUTHOR]

A paired dominating set P is a dominating set with the additional property that P has a perfect matching. While the maximum cardinality of a minimal dominating set in a graph G is called the upper domination number of G, denoted by Γ(G), the maximum cardinality of a minimal paired dominating set in G is called the upper paired domination number of G, denoted by Γpr(G). By Henning and Pradhan (2019), we know that Γpr(G) ≤ 2Γ(G) for any graph G without isolated vertices. We focus on the graphs satisfying the equality Γpr(G) = 2Γ(G). We give characterizations for two special graph classes: bipartite and unicyclic graphs with Γpr(G) = 2Γ(G) by using the results of Ulatowski (2015). Besides, we study the graphs with Γpr(G) = 2Γ(G) and a restricted girth. In this context, we provide two characterizations: one for graphs with Γpr(G) = 2Γ(G) and girth at least 6 and the other for C3-free cactus graphs with Γpr(G) = 2Γ(G). We also pose the characterization of the general case of C3-free graphs with Γpr(G) = 2Γ(G) as an open question. [ABSTRACT FROM AUTHOR]

We are given n balls and an unknown coloring of them with two colors. Our goal is to find a ball that belongs to the larger color class, or show that the color classes have the same size. We can ask sets of k balls as queries, and the problem has different variants, according to what the answers to the queries can be. These questions has attracted several researchers, but the focus of most research was the adaptive version, where queries are decided sequentially, after learning the answer to the previous query. Here we study the non-adaptive version, where all the queries have to be asked at the same time. [ABSTRACT FROM AUTHOR]

In this article we present theoretical and computational results on the existence of polyhedral embeddings of graphs. The emphasis is on cubic graphs. We also describe an efficient algorithm to compute all polyhedral embeddings of a given cubic graph and constructions for cubic graphs with some special properties of their polyhedral embeddings. Some key results are that even cubic graphs with a polyhedral embedding on the torus can also have polyhedral embeddings in arbitrarily high genus, in fact in a genus close to the theoretical maximum for that number of vertices, and that there is no bound on the number of genera in which a cubic graph can have a polyhedral embedding. While these results suggest a large variety of polyhedral embeddings, computations for up to 28 vertices suggest that by far most of the cubic graphs do not have a polyhedral embedding in any genus and that the ratio of these graphs is increasing with the number of vertices. [ABSTRACT FROM AUTHOR]

A family S of convex sets in the plane defines a hypergraph H = (S, E) with S as a vertex set and E as the set of hyperedges as follows. Every subfamily S'⊂ S defines a hyperedge in E if and only if there exists a halfspace h that fully contains S', and no other set of S is fully contained in h. In this case, we say that h realizes S' . We say a set S is shattered, if all its subsets are realized. The VC-dimension of a hypergraph H is the size of the largest shattered set. We show that the VC-dimension for pairwise disjoint convex sets in the plane is bounded by 3, and this is tight. In contrast, we show the VC-dimension of convex sets in the plane (not necessarily disjoint) is unbounded. We provide a quadratic lower bound in the number of pairs of intersecting sets in a shattered family of convex sets in the plane. We also show that the VC-dimension is unbounded for pairwise disjoint convex sets in Rd, for d ≥ 3. We focus on, possibly intersecting, segments in the plane and determine that the VC-dimension is at most 5. And this is tight, as we construct a set of five segments that can be shattered. We give two exemplary applications. One for a geometric set cover problem and one for a range-query data structure problem, to motivate our findings. [ABSTRACT FROM AUTHOR]

The majorization relation orders the degree sequences of simple graphs into posets called dominance orders. As shown by Ruch and Gutman (1979) and Merris (2002), the degree sequences of threshold and split graphs form upward-closed sets within the dominance orders they belong to, i.e., any degree sequence majorizing a split or threshold sequence must itself be split or threshold, respectively. Motivated by the fact that threshold graphs and split graphs have characterizations in terms of forbidden induced subgraphs, we define a class F of graphs to be dominance monotone if whenever no realization of e contains an element F as an induced subgraph, and d majorizes e, then no realization of d induces an element of F. We present conditions necessary for a set of graphs to be dominance monotone, and we identify the dominance monotone sets of order at most 3. [ABSTRACT FROM AUTHOR]

Let G. e. a digraph wihl cosicive eCge weighns as whlS as s and e be two veetic5s of G. The aai'lang nroblea (MP(stetes Ilow to aark -osa- cdgc-oe G wit h T and F, wliere every nnUi -torhinh; el sourni s will reae2laig8d il and the totol raiig- if the mnli-d edgns is aiaiaal. Wli-n Inadersing elii diea'ahle 7'-marked edges alioa-d re followed while F-aarded ednes should nnt. The basia a-nliia-idns and properties of the marking prols ge ne havn Igiee mvesteted i n [1]. This piapid diovidoe new cnntefouUons 13 td. a3-nng prablaa: as follows: (i- tho MP is NP-Complete own if the imde-lving digteph is an unweighted pinpry DAG; (It-the MP rannae ag a2lirrximaeed whhin tilean iw an anwelgytcd DAG and sven in an anweighted 'inary DAG with n vertices, where a is a constant. Moreover, a lower 'oand to the optimal solatisn of tDe IMF1 ie provide.. We also stud(tte eompleth v and ttal- lenges of the aaraing proMea in program flow graphs. [ABSTRACT FROM AUTHOR]

Network science has become a powerful tool to describe the structure and dynamics of real-world complex physical, biological, social, and technological systems. Largely built on empirical observations to tackle heterogeneous, temporal, and adaptive patterns of interactions, its intuitive and flexible nature has contributed to the popularity of the field. With pioneering work on the evolution of random graphs, graph theory is often cited as the mathematical foundation of network science. Despite this narrative, the two research communities are still largely disconnected. In this commentary, we discuss the need for further cross-pollination between fields – bridging the gap between graphs and networks – and how network science can benefit from such influence. A more mathematical network science may clarify the role of randomness in modeling, hint at underlying laws of behavior, and predict yet unobserved complex networked phenomena in nature. What is the path towards a physical theory of complex networked systems? With an eye to the historical maths-physics duality, and an outlook towards the future, this commentary discusses promises and challenges accompanying the convergence of formal graph theory and data-inspired network science. [ABSTRACT FROM AUTHOR]

The cabreves are notarial documents prepared between the 13th and 19th centuries in the Catalan and Valencian regions of Spain. These historical records were published before the first cadastral maps and contain geographical information that could help spatially reconstruct historical landscapes. However, these documents have not been used to their full potential mainly because of their semi-structured and complex nature. In this article, we propose a new graph-based interactive methodology for partially reconstructing historical landscapes. We have successfully applied this methodology for reconstructing the historical landscape of the Barony of Sella in the 18th century and the methodology has also helped us locate "El Poblet," a previously unknown archeological site abandoned after the expulsion of the Moriscos in 1609. [ABSTRACT FROM AUTHOR]

A graph G is almost hypohamiltonian (a.h.) if G is non-hamiltonian, there exists a vertex w in G such that G -- w is non-hamiltonian, and G -- v is hamiltonian for every vertex v ≠ w in G. The second author asked in [J. Graph Theory 79 (2015) 63-81] for all orders for which a.h. graphs exist. Here we solve this problem. To this end, we present a specialised algorithm which generates complete sets of a.h. graphs for various orders. Furthermore, we show that the smallest cubic a.h. graphs have order 26. We provide a lower bound for the order of the smallest planar a.h. graph and improve the upper bound for the order of the smallest planar a.h. graph containing a cubic vertex. We also determine the smallest planar a.h. graphs of girth 5, both in the general and cubic case. Finally, we extend a result of Steffen on snarks and improve two bounds on longest paths and longest cycles in polyhedral graphs due to Jooyandeh, McKay, Östergård, Pettersson, and the second author. [ABSTRACT FROM AUTHOR]

Let f : V → ℤk be a vertex labeling of a hypergraph H = (V, E). This labeling induces an edge labeling of H defined by f(e) = ∑v∈e f(v), where the sum is taken modulo k. We say that f is k-cordial if for all a, b ∈ ℤk the number of vertices with label a differs by at most 1 from the number of vertices with label b and the analogous condition holds also for labels of edges. If H admits a k-cordial labeling then H is called k-cordial. The existence of k-cordial labelings has been investigated for graphs for decades. Hovey (1991) conjectured that every tree T is k-cordial for every k ≥ 2. Cichacz, Görlich and Tuza (2013) were first to investigate the analogous problem for hypertrees, that is, connected hypergraphs without cycles. The main results of their work are that every k-uniform hypertree is k-cordial for every k ≥ 2 and that every hypertree with n or m odd is 2-cordial. Moreover, they conjectured that in fact all hypertrees are 2-cordial. In this article, we confirm the conjecture of Cichacz et al. and make a step further by proving that for k ∈ {2, 3} every hypertree is k-cordial. [ABSTRACT FROM AUTHOR]

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu (2017) recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number of G is the minimum number of vertices and edges whose deletion leaves the resulting graph without a fractional perfect matching. In this paper, we obtain the fractional matching preclusion number and the fractional strong matching preclusion number for generalized augmented cubes. In addition, all the optimal fractional strong matching preclusion sets of these graphs are categorized. [ABSTRACT FROM AUTHOR]

Edge-connectivity is a classic measure for reliability of a network in the presence of edge failures. k-restricted edgeconnectivity is one of the refined indicators for fault tolerance of large networks. Matching preclusion and conditional matching preclusion are two important measures for the robustness of networks in edge fault scenario. In this paper, we show that the DCell network Dk, n is super-γ for k ≥ 2 and n ≥2, super-γ2 for k ≥ 3 and n ≥ 2, or k = 2 and n = 2, and super-γ3 for k ≥ 4 and n ≥ 3. Moreover, as an application of k-restricted edge-connectivity, we study the matching preclusion number and conditional matching preclusion number, and characterize the corresponding optimal solutions of Dk,n. In particular, we have shown that D1;n is isomorphic to the (n, k)-star graph Sn+1,2 for n ≥ 2. [ABSTRACT FROM AUTHOR]

The seminal book on graph theory by Dénes Kőnig, published in the year 1936, collected notions and results from precursory works from the mid to late nineteenth century by Hamilton, Cayley, Sylvester and others. More importantly, Kőnig himself contributed many of his own results that he had obtained in the more than twenty years that he had been working on this subject matter. What is noteworthy is the fact that the fundamentals of what he calls directed graphs are taken almost exhaustively from Paul Hertz' 1922 article on structural reasoning about sentences of the form. This is not a fact that is well known in logical circles, even though Kőnig fully acknowledges this in his book. In view of the numerous trends in the recent decades to describe and explicate logical matters by means of graphs, the fact that it was Hertz' foundation of structural reasoning that informed basic notions of graph theory in the first place is highly significant. The main goal of this paper is to summarize Hertz' article and demonstrate how Kőnig integrates the notions and results presented therein in his book. This is followed by an exposition of how and when Hertz' results were reinvented in terms of graph theory. A critical discussion of the opinion expressed by both Hertz and Kőnig that the more general sentences of the form , introduced by Hertz in a companion article in 1923, cannot be interpreted by graphs concludes this paper. [ABSTRACT FROM AUTHOR]

Opportunistic multihop networks with mobile relays recently have drawn much attention from researchers across the globe due to their wide applications in various challenging environments. However, because of their peculiar intrinsic features like lack of continuous connectivity, network partitioning, highly dynamic behavior, and long delays, it is very arduous to model and effectively capture the temporal variations of such networks with the help of classical graph models. In this work, we utilize an evolving graph to model the dynamic network and propose a matrix‐based algorithm to generate all minimal path sets between every node pair of such network. We show that these time‐stamped‐minimal‐path sets (TS‐MPS) between each given source‐destination node pair can be used, by utilizing the well‐known Sum‐of‐Disjoint Products technique, to generate various reliability metrics of dynamic networks, ie, two‐terminal reliability of dynamic network and its related metrics, ie, two‐terminal reliabilities of the foremost, shortest, and fastest TS‐MPS, and Expected Hop Count. We also introduce and compute a new network performance metric−Expected Slot Count. We use two illustrative examples of dynamic networks, one of four nodes, and the other of five nodes, to show the salient features of our technique to generate TS‐MPS and reliability metrics. [ABSTRACT FROM AUTHOR]

Abstract Asymptotic stability of linear nabla Riemann–Liouville (q, h)-fractional difference equation is investigated in this paper. A Liapunov functional is constructed for the fractional difference equation. The sufficient condition for the asymptotic stability of considered equations is proposed. The results are illustrated with the corresponding numerical examples. [ABSTRACT FROM AUTHOR]

Abstract So far, research into pubic goods games has been limited to studying the effects of leadership in an experimental works. The results found differ according to the population studied, the number of participants and the country chosen, which makes ideas imprecise when it comes to understanding how cooperation evolves. In this article we try to generalize these works by introducing an agent-based model to simulate interactions in public goods games on a graph, and study the impact of leadership by example on the evolution of cooperation among selfish individuals in a scale-free network. Consistent with recent experimental studies, our results show that leading by example leads to a significant increase in the overall contribution and the group's welfare, as compared to the situation without leadership. We have demonstrated also that strong leaders have an important role in promoting optimal cooperation in public goods games and consequently they bring more welfare to their groups. [ABSTRACT FROM AUTHOR]

Abstract This paper addresses the asynchronous H ∞ control problem for a class of continuous-time semi-Markov jump linear systems. Under the assumption that the system mode is not accessible, we introduce a discrete-state and continuous-time process which is related to the system mode by a conditional probability as a switching signal of the controller. By constructing a semi-Markov-based Lyapunov funcational, a sufficient condition to ensure the stability of the system with a prescribed H ∞ performance is established. In addition, an equivalent statement is derived by introducing a slack variable, and the asynchronous controller is designed. Two examples are presented to illustrate the effectiveness of the proposed new design method. [ABSTRACT FROM AUTHOR]

Abstract A function f : V (G) → { 0 , 1 , ... , k } is called a k -rainbow independent dominating function of G if V i = { x ∈ V (G) : f (x) = i } is independent for 1 ≤ i ≤ k , and for every x ∈ V 0 it follows that N (x) ∩ V i ≠ ∅, for every i ∈ [ k ]. The k -rainbow independent domination number, γ ri k (G), of a graph G is the minimum of w (f) = ∑ i = 1 k | V i | over all such functions. In this paper we show that the problem of determining whether a graph has a k -rainbow independent dominating function of a given weight is NP-complete for bipartite graphs and that there exists a linear-time algorithm to compute γ ri k (G) of trees. In addition, sharp bounds for the k -rainbow independent domination number of the lexicographic product are presented, as well as the exact formula in the case k = 2. [ABSTRACT FROM AUTHOR]

A network's diagnosability is the maximum number of faulty vertices that the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The g -good-neighbor conditional diagnosability is the maximum cardinality of g -good-neighbor conditional fault-set that the system is guaranteed to identify. The g -good-neighbor conditional diagnosability of E H (s, t) under the PMC model has been proposed by Liu et al. [Liu, X. Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol. 35, 390–393]. However, the method by Liu et al. [Liu, X. Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol. 35, 390–393] is too complicated to follow, and it is not complete. We will propose a complete method to establish the g -good-neighbor conditional diagnosability of E H (s, t) under the PMC model by optimizing the structure of the proof in [Liu, X. Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol. 35, 390–393] and adding the missing case. Also we add a ratio in a table to represent the probability that a faulty set with size s contains all neighbors of any vertex, which is very low. Moreover, we mainly establish the g -good-neighbor conditional diagnosability for exchanged hypercube E H (s, t) under the comparison model. [ABSTRACT FROM AUTHOR]

The underlying topology of an interconnection network can be modeled by a digraph D = (V, A) ⁠. A strongly connected digraph D is maximally arc-connected if its arc-connectivity is equal to its minimum degree. The maximally arc-connected tolerance m λ (D) to arc-faults of a maximally arc-connected digraph D is the maximum integer f, for which D − S is still maximally arc-connected for any set S ⊆ A (D) with | S | ≤ f ⁠. The index m λ (D) is used to measure the reliability of networks. In this paper, we present upper and lower bounds on m λ (D) ⁠. More refined bounds are obtained under some conditions, from which the exact values of m λ (D) are determined for some networks modeled by digraphs. [ABSTRACT FROM AUTHOR]

There are a lot of centrality measures that have been introduced for networks. One of them is betweenness centrality. It is a measure of the influence of a vertex over the flow of information between all pairs of vertices. This information flows over the shortest paths between these vertices. The fact that any vertex has a high value of centrality indicates that what level this vertex is in connection with vertices which are not adjacent with each other. Since this vertex controls flows of information, it has a potential role in the network. In this paper, we study on the betweenness centrality of some complementary prism graphs. [ABSTRACT FROM AUTHOR]

Consider a general path planning problem of a robot on a graph with edge costs, where each node has a Boolean value of success or failure (with respect to some task) with a given probability. The objective is to plan a path for the robot on the graph that minimizes the expected cost until success. In this paper, it is our goal to bring a foundational understanding to this problem. We start by showing how this problem can be optimally solved by formulating it as an infinite-horizon Markov decision process, but with an exponential space complexity. We then formally prove its NP-hardness. To address the space complexity, we then propose a path planner, using a game-theoretic framework, that asymptotically gets arbitrarily close to the optimal solution. Moreover, we also propose two fast and nonmyopic path planners. To show the performance of our framework, we do extensive simulations for two scenarios: a rover on Mars searching for an object for scientific studies, and a robot looking for a connected spot to a remote station (with real data from downtown San Francisco). Our numerical results show a considerable performance improvement over existing state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

Abstract A graph G is said to be determined by its spectrum if any graph having the same spectrum as G is isomorphic to G. Let K n ∖ P ℓ be the graph obtained from K n by removing edges of P ℓ , where P ℓ is a path of length ℓ − 1 which is a subgraph of a complete graph K n. Cámara and Haemers (2014) conjectured that K n ∖ P ℓ is determined by its adjacency spectrum for every 2 ≤ ℓ ≤ n. In this paper we show that the conjecture is true for 7 ≤ ℓ ≤ 9. [ABSTRACT FROM AUTHOR]

Abstract Let G = (V , E) be a simple graph without isolated vertices. A set S ⊆ V is called a paired-dominating set if every vertex in V ∖ S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of G , denoted by γ p r (G) , is the minimum cardinality of a paired-dominating set of G. We show that γ p r (G) ≤ 4 n ∕ 7 if G is a claw-free graph of order n with minimum degree at least three. The statement partly confirms the conjecture proposed by Goddard and Henning in 2009. [ABSTRACT FROM AUTHOR]

In this paper, we propose a simple and effective geometric model fitting method to fit and segment multi-structure data even in the presence of severe outliers. We cast the task of geometric model fitting as a representative mode-seeking problem on hypergraphs. Specifically, a hypergraph is first constructed, where the vertices represent model hypotheses and the hyperedges denote data points. The hypergraph involves higher-order similarities (instead of pairwise similarities used on a simple graph), and it can characterize complex relationships between model hypotheses and data points. In addition, we develop a hypergraph reduction technique to remove “insignificant” vertices while retaining as many “significant” vertices as possible in the hypergraph. Based on the simplified hypergraph, we then propose a novel mode-seeking algorithm to search for representative modes within reasonable time. Finally, the proposed mode-seeking algorithm detects modes according to two key elements, i.e., the weighting scores of vertices and the similarity analysis between vertices. Overall, the proposed fitting method is able to efficiently and effectively estimate the number and the parameters of model instances in the data simultaneously. Experimental results demonstrate that the proposed method achieves significant superiority over several state-of-the-art model fitting methods on both synthetic data and real images. [ABSTRACT FROM AUTHOR]

The discovery and analysis of network patterns are central to the scientific enterprise. In the present work, we developed and evaluated a new approach that learns the building blocks of graphs that can be used to understand and generate new realistic graphs. Our key insight is that a graph's clique tree encodes robust and precise information. We show that a Hyperedge Replacement Grammar (HRG) can be extracted from the clique tree, and we develop a fixed-size graph generation algorithm that can be used to produce new graphs of a specified size. In experiments on large real-world graphs, we show that graphs generated from the HRG approach exhibit a diverse range of properties that are similar to those found in the original networks. In addition to graph properties like degree or eigenvector centrality, what a graph “looks like” ultimately depends on small details in local graph substructures that are difficult to define at a global level. We show that the HRG model can also preserve these local substructures when generating new graphs. [ABSTRACT FROM AUTHOR]

Let p: X → X be a regular covering projection of connected graphs, where CTp denotes the group of covering transformations. Suppose that a group G ≤ Aut X lifts along p to a group G ≤ Aut X. The corresponding short exact sequence id → CTp → G → G → id is split sectional over a G-invariant subset of vertices Ω ⊆ V (X) if there exists a sectional complement, that is, a complement G to CTp with a G-invariant section Ω ⊂ V (X) over Ω. Such lifts do not split just abstractly but also permutationally in the sense that they enable a nice combinatorial description. Sectional complements are characterized from several viewpoints. The connection between the number of sectional complements and invariant sections on one side, and the structure of the split extension itself on the other, is analyzed. In the case when CTp is abelian and the covering projection is given implicitly in terms of a voltage assignment on the base graph X, an efficient algorithm for testing whether G has a sectional complement is presented. Efficiency resides on avoiding explicit reconstruction of the covering graph and the lifted group. The method extends to the case when CTp is solvable. [ABSTRACT FROM AUTHOR]

This paper extends and updates the survey [J. Czap, S. Jendrol', Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2703] on facial colorings. Different types of colorings of plane graphs are discussed in their vertex, edge, total, and list versions. [ABSTRACT FROM AUTHOR]

We prove that if two nonnegative matrices are strong shift equivalent, the associated stable Cuntz-Krieger algebras with generalized gauge actions are conjugate. The proof is done by a purely functional analytic method and based on constructing imprimitivity bimodule from bipartite directed graphs through strong shift equivalent matrices, so that we may clarify K-theoretic behaviour of the stable isomorphism between the associated stable Cuntz-Krieger algebras. We also examine our machinery for the matrices obtained by state splitting graphs, so that topological conjugacy of the topological Markov shifts is described in terms of some equivalence relation of the Cuntz-Krieger algebras with canonical masas and the gauge actions without stabilization. [ABSTRACT FROM AUTHOR]

Abstract Fault diagnosis of systems is an important area of study in the design and maintenance of multiprocessor systems. A new measure for fault diagnosis of systems, namely, h -edge tolerable diagnosability, is the maximum number of faulty nodes that a system G can guarantee to locate when the number of faulty links does not exceed h , denoted by t h e (G). Particularly, t 0 e (G) is the traditional diagnosability of G. Chang et al. (2005) [5] determined the traditional diagnosabilities of regular graphs. In this paper, we establish the h -edge tolerable diagnosabilities of regular graphs under the PMC model and the MM⁎ model, which extends their results and provides a more precise characterization for the fault diagnosis capability of regular graphs. As applications, the h -edge tolerable diagnosabilities of many networks are determined under the PMC model and the MM⁎ model. [ABSTRACT FROM AUTHOR]