Search

In this paper, we discuss spectrum and energy of Arithmetic function signed graphs with respect to an arithmetical function and present some results. [ABSTRACT FROM AUTHOR]

Given a group G, we define the power graph P(G) as follows: the vertices are the elements of G and two vertices x and y are joined by an edge if ⟨x⟩ ⊆ ⟨y⟩ or ⟨y⟩ ⊆ ⟨x⟩. Obviously the power graph of any group is always connected, because the identity element of the group is adjacent to all other vertices. We consider κ(G), the number of spanning trees of the power graph associated with a finite group G. In this paper, for a finite group G, first we represent some properties of P(G), then we are going to find some divisors of κ(G), and finally we prove that the simple group A6= L2(9) is uniquely determined by tree-number of its power graph among all finite simple groups. [ABSTRACT FROM AUTHOR]

The restrained captive domination number (RCDN), denoted by γ Rca (G) , is a new definition of domination number in graphs introduced in this article. If D is a captive dominating set and G [ V − D ] has no isolated vertex, then D is a restrained captive dominating set (RCDS) of graph G. Furthermore, some properties, theorems, and propositions are determined. The inverse RCDN is introduced too. The RCDN in complement graphs is discussed. Finally, the RCDS of some graphs is determined. We have explained that if the graph has pendent vertex, then it has no RCDN. [ABSTRACT FROM AUTHOR]

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]

The independence number of a graph is one of the basic numerical characteristics of a graph. Additionally, it is one of the most fundamental and well-studied graph parameters. It is also used the proof the computational complexity of many theoretical problems. Thus, many independence-type parameters have been studied in the literature. The independence saturation number IS(G) is one of the fundamental parameters introduced by Subramanian (Arumugam & Subramanian, 2007). In this paper, we examine the independence saturation numbers for splitting graph S(G) when G is a specific type of graphs is computed, and exact formulae are derived. [ABSTRACT FROM AUTHOR]

Graph theory has turned out to be one of the most significant mathematical methods for studying and analyzing network design. For various systems and contexts, networks may be essential frameworks. Networks have become extremely popular as they are now common ground for multidisciplinary research from chemistry to social sciences. In applied mathematics, graphs are used on the differential equations and partial differential equations. Since, under certain cases, the average parameters are more efficient than other similar measures based on the worst-case condition, in this paper, a novel average parameter is defined and studied for connected 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]

We consider the problemof coloring a 3-colorable graph in polynomial time using as few colors as possible. We first present a new combinatorial algorithmusing Õ(n4/11) colors. This is the first combinatorial improvement since Blum's Õ(n3/8) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes immediately with recent semi-definite programming approaches, and improves the best bound for the polynomial time algorithmfor the coloring of 3-colorable graphs from O(n0.2072) colors by Chlamtac from FOCS'07 to O(n0.2049) colors. Next, we develop a new recursion tailored for combination with semi-definite approaches, bringing us further down to O(n0.19996) colors. [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]

Let X, Y, S be closed connected surfaces and τ × β a diagonal involution on X × Y where τ and β are free involutions on X and Y, respectively. In this work we study when the triple (X ×Y, τ ×β, S) satisfies the Borsuk-Ulam property. The problem is formulated in terms of an algebraic diagram, involving the 2-string braid group B2(S). [ABSTRACT FROM AUTHOR]

With the advances in computing resources, the processing of huge amount of data becomes possible. However, the human ability to identify patterns from such data has not scaled accordingly. Consequently, efficient computational approaches for condensing and simplifying data are becoming essential for uncovering actionable insights, especially the big social networks. Many large datasets analyzed today are represented with the help of graphs. In many real-world applications, summarizing large graphs is beneficial to achieve a number of advantages, including 1) significant speedup for graph algorithms, 2) graph storage space reduction, 3) faster network transmission, 4) improved data privacy, 5) more effective graph visualization, etc. All these benefits can be obtained from the summarized graph, if it is summarized accurately. The quality of the summary graph is mostly measured using the Reconstruction Error (RE). In the existing literature, RE is a very challenging task. Most of the approaches investigated so far ending up with high value of RE. Hence, the summarized graph does not express the original graph completely due to the high value of the RE. Therefore, in this work we have examined how can we summarize a big graph structure into a compact summary by reducing its RE and ensuring its usefulness. For this task, we have proposed a novel graph summarization approach, called g-Sum, to calculate the graph structure summaries while minimizing RE and compare to the existing work in the domain. The functionality of the g-Sum is decomposed into three different, but interlinked phases; (1)- graph dataset pre-processing; (2)- graph partitioning; and (3)- graph summarization. We have performed an extensive series of experiments on different real-world social graph dataset, including Ego-Facebook, Enron Email and Web-Stanford graph datasets. The computed results show the effectiveness of the g-Sum and also compared with the state-of-the-art graph summarization approaches, S2L and GraSS. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

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]

The relationship between Graph Theory and Topological Space has recently developed greatly, as researchers have been able to find solutions to some problems in daily life by transforming the problem into a graph and then generating a topological space and thus facilitating reading the problem and solving it. The researchers also studied the generation of graph from topological spaces.In this article we will present two types of relations on the edges set that generate topological spaces, and we will discuss some properties of this topology, and we will study discuss the method of returning from the topological space to the graphs through using previous relationships. [ABSTRACT FROM AUTHOR]

If a network modeled by a graph, then there are various graph theoretical parameters used to express the vulnerability of communication networks. One of them is the concept of integrity. In this paper, we determine exact values for the integrity of wheel related graphs. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Zhejiang University (Science Edition) is the property of Journal of Zhejiang University (Science Edition) Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Nowadays, open-source graph databases do not include an inherent mechanism for data relocation that would be based on their usage. They often do not offer even appropriate monitoring that could help to make such a decision. Information about data utilization could, however, work as an input to some decision-making process about more suitable data regrouping that could be much more efficient in terms of intra-network communication. Therefore, we created a module for the graph computational framework TinkerPop that logs traffic generated by the user queries. These logged records serve as an input for the algorithm of Adaptive Partitioning that we enhanced with better balancing, avoidance of local optima and the notion of weighted graphs. This approach yields a 70–80% improvement in intra-network communication, which is comparable to other methods, namely Ja-be-Ja, that offers similar results but has higher computational demands. [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]

This paper concerns the issues of exponential stability in Lagrange sense for a class of stochastic Cohen--Grossberg neural networks (SCGNNs) with Markovian jump and mixed time delay effects. A systematic approach of constructing a global Lyapunov function for SCGNNs with mixed time delays and Markovian jumping is provided by applying the association of Lyapunov method and graph theory results. Moreover, by using some inequality techniques in Lyapunovtype and coefficient-type theorems we attain two kinds of sufficient conditions to ensure the global exponential stability (GES) through Lagrange sense for the addressed SCGNNs. Ultimately, some examples with numerical simulations are given to demonstrate the effectiveness of the acquired result. [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]

Subnetwork with two nodes shared with entire ventilation network can be separated as its part. For the network under common ventilation conditions, one of these nodes will become the subnetwork starting node, while the other will be the subnetwork end node. According to the graphs theory, such a piece of the network can be considered as a subgraph of the graph representing the entire ventilation network. A special feature of that subgraph is lack of predecessors of the subnetwork starting node and lack of successors of the subnetwork end node. Ventilation district of a mine may be often treated as a subnetwork. Vicinity is a part of the network which is not separated as subnetwork. In the case of a ventilation district its vicinity forces air flow through the district. The alternative characteristic curve of the vicinity can therefore be compared to the characteristics curve of a fictional fan that forces the airflow in the district. The alternative characteristics (later in the text: the characteristics) of the vicinity of the ventilation district in an underground mine strongly influence air quantity and therefore play a crucial role in the reduction of methane, fire and thermal hazards. The role of these characteristics and proper selection of their approximating function were presented in the article. The reduction of resistance of an intake stopping (having influence on entire resistance of a ventilation district) produces increased airflow in the district. This changes of airflow in the district caused by a variation in internal resistance (e.g. by opening an internal regulation stopping) depends on the characteristic of the vicinity of the district. Proper selection of its approximating function is also important for this matter. The methods of determination of the alternative characteristic curve of the district vicinity are presented. From these procedures it was possible to obtain the results of air quantities and differences in isentropic potentials between an inlet and an outlet to/from the ventilation district. Following this, the characteristics were determined by graphic and analytic methods. It was proved that, in contrast to flat vicinity characteristics, steep ones have a smaller influence on the airflow modification in the district (which are caused by a regulation of the district resistance). The characteristic curve of the vicinity determines the ability to regulate air quantity and velocity in the district. [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]

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log² n) factor in Ö (m +n3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time Ö (m + n²). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log² n)-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time. [ABSTRACT FROM AUTHOR]

We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given an n-vertex graph G along with k source-sink pairs, and the goal is to find the minimum cardinality subset of edges whose removal separates all source-sink pairs. The sparsest cut problem has the same input, but the goal is to find a subset of edges to delete so as to minimize the ratio of the number of deleted edges to the number of source-sink pairs that are separated by this deletion. The natural linear programming relaxation for multicut corresponds, by LP-duality, to the well-studied maximum (fractional) multicommodity flow problem, while the standard LP-relaxation for sparsest cut corresponds to maximum concurrent flow. Therefore, the integrality gap of the linear programming relaxation for multicut/sparsest cut is also the flow-cut gap: the largest gap, achievable for any graph, between the maximum flow value and the minimum cost solution for the corresponding cut problem. Our first result is that the flow-cut gap between maximum multicommodity flow and minimum multicut is Ω(n1/7) in directed graphs. We show a similar result for the gap between maximum concurrent flow and sparsest cut in directed graphs. These results improve upon a long-standing lower bound of Ω(log n) for both types of flow-cut gaps. We notice that these polynomially large flow-cut gaps are in a sharp contrast to the undirected setting where both these flow-cut gaps are known to be Θ(log n). Our second result is that both directed multicut and sparsest cut are hard to approximate to within a factor of 2Ω(log1-є n) for any constant є > 0, unless NP⊆ZPP. This improves upon the recent Ω(log n/ log log n)-hardness result for these problems. We also show that existence of PCP's for NP with perfect completeness, polynomially small soundness, and constant number of queries would imply a polynomial factor hardness of approximation for both these problems. All our results hold for directed acyclic graphs. [ABSTRACT FROM AUTHOR]

We give a O(√log n)-approximation algorithm for the SPARSEST CUT, EDGE EXPANSION, BALANCED SEPARATOR, and GRAPH CONDUCTANCE problems. This improves the O(log n)-approximation of Leighton and Rao (1988).We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets in Rd, whose proof makes essential use of a phenomenon called measure concentration. We also describe an interesting and natural "approximate certificate" for a graph's expansion, which involves embedding an n-node expander in it with appropriate dilation and congestion.We call this an expander flow. [ABSTRACT FROM AUTHOR]

It is known that if P and NP are different then there is an infinite hierarchy of different complexity classes that lie strictly between them. Thus, if P ≠ NP, it is not possible to classify NP using any finite collection of complexity classes. This situation has led to attempts to identify smaller classes of problems within NP where dichotomy results may hold: every problem is either in P or is NP-complete. A similar situation exists for counting problems. If P≠#P, there is an infinite hierarchy in between and it is important to identify subclasses of #P where dichotomy results hold. Graph homomorphism problems are a fertile setting in which to explore dichotomy theorems. Indeed, Feder and Vardi have shown that a dichotomy theorem for the problem of deciding whether there is a homomorphism to a fixed directed acyclic graph would resolve their long-standing dichotomy conjecture for all constraint satisfaction problems. In this article, we give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs. Let H be a fixed directed acyclic graph. The problem is, given an input digraph G, determine how many homomorphisms there are from G to H. We give a graph-theoretic classification, showing that for some digraphs H, the problem is in P and for the rest of the digraphs H the problem is #P-complete. An interesting feature of the dichotomy, which is absent from previously known dichotomy results, is that there is a rich supply of tractable graphs H with complex structure. [ABSTRACT FROM AUTHOR]