Search

A coloring C = (V1,...,Vk) of G partitions the vertex set V (G) into independent sets Vi which are said to be color classes with respect to the coloring C. A vertex v is said to have a dominator (dom) color class in C if there is color class Vi such that v is adjacent to all the vertices of Vi and v is said to have an anti-dominator (anti-dom) color class in C if there is color class Vj such that v is not adjacent to any vertex of Vj. Dominator coloring of G is a coloring C of G such that every vertex has a dom color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G, denoted by χd(G). Global Dominator coloring of G is a coloring C of G such that every vertex has a dom color class and an anti-dom color class. The minimum number of colors required for a global dominator coloring of G is called the global dominator chromatic number of G, denoted by χgd(G). In this paper, we give a counterexample for the conjecture posed in [I. Sahul Hamid, M.Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39 (2019), 325-339] that for a graph G, if Xgd(G) = 2χd(G), then G is a complete multipartite graph. We deduce upper and lower bound for the global dominator chromatic number of Mycielskian of the graph G in terms of dominator chromatic number of G. [ABSTRACT FROM AUTHOR]

This work is devoted to exploring proof abilities in Graph Theory of undergraduate students of the Degree in Computer Engineering and Technology of the University of Seville. To do this, we have designed a questionnaire consisting of five open-ended items that serve as instrument to collect data concerning their proof skills when dealing with graphs. We have thus analysed them adapting the methodology for computing the degrees of acquisition of the Van Hiele levels. Our analysis leads to different proof profiles of Graph Theory students whose characteristics provide empirical support to consider proof levels in Graph Theory from the perspective of the Van Hiele model. [ABSTRACT FROM AUTHOR]

The investigation into the domination problem and the associated subset problem of graphs is a focal point in graph theory research, sparking widespread interest and extensive exploration. This paper mainly studies the Italian domination of the strong product of two cycles. By constructing recursive Italian dominating functions, a well-defined bound for the Italian domination number in Cn Cm is obtained. Furthermore, through mathematical derivation and proof, the precise Italian domination number of C3 Cm is determined. [ABSTRACT FROM AUTHOR]

In our earlier work, we suggested an axiomatic framework for deducing the fundamental entities which constitute the building block of the elementary particles in physics. The basic concept of this theory, named apriorics, is the ontological structure (OS)—an undirected simple graph satisfying specified conditions. The vertices of this graph represent the fundamental entities (FEs), its edges are binary compounds of the FEs (which are the fundamental bosons and fermions), and the structures constituting more than two connected vertices are composite particles. The objective of this paper is to focus the attention on several mathematical theorems and ideas associated with such graphs of order n, including their enumeration, showing what is the information content of apriorics. [ABSTRACT FROM AUTHOR]

In addition, they sometimes have solutions to equations such as Graph HT ht , and they are useful for answering questions such as: When is Graph HT ht divisible by a large power of 2? A I p i -adic integer is a sum such as Graph HT ht where each I d SB i sb i is an integer in the range 0 through Graph HT ht In contrast to the reals, in which two numbers are close when their first several digits are the same, two I p i -adic numbers are close when their last several digits are the same. I i is I holonomic i if there is a smooth periodic function I f i ( I t i ) such that Graph HT ht . [Extracted from the article]

Mechanisms coupling the chemical reactions of oxidation and ATP synthesis in cellular metabolism by the fundamental biological process of oxidative phosphorylation (OX PHOS) in mitochondria provide > 90% of the energy requirements in living organisms. Mathematical graph theory methods have been extensively used to characterize various metabolic, regulatory, and disease networks in biology. However, networks of energy coupling mechanisms in OX PHOS have not been represented and analyzed previously by these approaches. Here, the problem of biological energy coupling is translated into a graph-theoretical framework, and all possible coupling schemes between oxidation and ATP synthesis are represented as graphs connecting these processes by various intermediates or states. The problem is shown to be transformed into the hard problem of finding a Hamiltonian tour in the networks of possible constituent mechanisms, given the constraints of a cyclical nature of operation of enzymes and biological molecular machines. Accessible mathematical proofs of three theorems that guarantee sufficient conditions for the existence of a Hamiltonian cycle in simple graphs are provided. The results of the general theorems are applied to the set of possible coupling mechanisms in OX PHOS and shown to (1) unequivocally differentiate between the major theories and mechanisms of energy coupling, (2) greatly reduce the possibilities for detailed consideration, and (3) deduce the biologically selected mechanism using additional constraints from the cumulative experimental record. Finally, an algorithm is constructed to implement the graph-theoretical procedure. In summary, the enormous power and generality of mathematical theorems and approaches in graph theory are shown to help solve a fundamental problem in biology. [ABSTRACT FROM AUTHOR]

Let G be a finite, undirected and simple graph. A proper vertex coloring of a graph of G is equitable if the sizes of color classes differ by atmost 1. The equitable chromatic number of a graph G, denoted by X=(G), is the minimum k such that G is equitably k-colorable. We shall discuss about an equitable coloring for union of two graphs. [ABSTRACT FROM AUTHOR]

The chromatic number, x(G) of a graph G is the minimum number of colours used in a proper colouring of G. In an improper colouring, an edge uv is bad if the colours assigned to the end vertices of the edge is the same. Now, if the available colours are less than that of the chromatic number of graph G, then colouring the graph with the available colours lead to bad edges in G. The number of bad edges resulting from a δ(k)-colouring of G is denoted by bk(G). In this paper, we use the concept of δ(k)-colouring and determine the number of bad edges in Cartesian product of some graphs. [ABSTRACT FROM AUTHOR]

In this paper, we initiate the study of total outer-convex domination as a new variant of graph domination and we show the close relationship that exists between this novel parameter and other domination parameters of a graph such as total domination, convex domination, and outer-convex domination. Furthermore, we obtain general bounds of total outer-convex domination number and, for some particular families of graphs, we obtain closed formulas. [ABSTRACT FROM AUTHOR]

A signed graph is an ordered pair Σ = (G,σ), where G = (V, E) is the underlying graph of Σ with a signature function σ : E → {1, -1}. In this article, we define the nth power of a signed graph and discuss some properties of these powers of signed graphs. As we can define two types of signed graphs as the power of a signed graph, necessary and sufficient conditions are given for an nth power of a signed graph to be unique. Also, we characterize balanced power signed graphs. [ABSTRACT FROM AUTHOR]

The role of this paper is to evaluate the process of calculating the Maximal Matching in the Fractal Graph especially Von Koch Curve and Koch Snowflake. Here it analyzes the characteristics, construction, properties, nature, implementation, Iteration and uses of the famous Fractal Graph like Von Koch Curve and Koch Snowflake. Here to explain how the Fractal Graph can be constructed and implemented. By using Proof of Mathematical Induction methods, it evaluates the Maximal Matching Cardinality of Von Koch Curve and Koch Snowflake. Cardinality shows that the number of vertices selected for Maximal Matching. Also this paper shows that the value of cardinality remains the constant ratio for all Iteration of the Fractal Graph. It shows that the application of Maximal Matching cardinality value is useful for many areas like Construction Field, Designing of Computer Architecture field, Focus of Camera, Consumption of raw material in construction Sight and so on. [ABSTRACT FROM AUTHOR]

Abstract A graph is q -planar if it can be drawn in the plane so that each edge is crossed by at most q other edges. For fixed integers q ≥ 1 and k ≥ 2, it is proven that 2 (n − 1) k + o (n) is an asymptotically tight upper bound on the sum of the k -th powers of the degrees of any simple q -planar graph with order n. As a result, an open problem listed at the end of the paper J. Czap, J. Harant, D. Hudák, Discrete Appl. Math. 165 (2014) 146–151 is solved. [ABSTRACT FROM AUTHOR]

Abstract A graph G is H -saturated for a graph H , if G does not contain a copy of H but adding any new edge to G results in such a copy. An H -saturated graph on a given number of vertices always exists and the properties of such graphs, for example their highest density, have been studied intensively. A graph G is H -induced-saturated if G does not have an induced subgraph isomorphic to H , but adding an edge to G from its complement or deleting an edge from G results in an induced copy of H. It is not immediate anymore that H -induced-saturated graphs exist. In fact, Martin and Smith (2012) showed that there is no P 4 -induced-saturated graph. Behrens et al. (2016) proved that if H belongs to a few simple classes of graphs such as a class of odd cycles of length at least 5, stars of size at least 2, or matchings of size at least 2, then there is an H -induced-saturated graph. This paper addresses the existence question for H -induced-saturated graphs. It is shown that Cartesian products of cliques are H -induced-saturated graphs for H in several infinite families, including large families of trees. A complete characterization of all connected graphs H for which a Cartesian product of two cliques is an H -induced-saturated graph is given. Finally, several results on induced saturation for prime graphs and families of graphs are provided. [ABSTRACT FROM AUTHOR]

Abstract We study the independence number of a product of Kneser graph K (n , k) with itself, where we consider all four standard graph products. The cases of the direct, the lexicographic and the strong product of Kneser graphs are not difficult (the formula for α (K (n , k) ⊠ K (n , k)) is presented in this paper), while the case of the Cartesian product of Kneser graphs is much more involved. We establish a lower bound and an upper bound for the independence number of K (n , 2) □ K (n , 2) , which are asymptotically tending to n 3 ∕ 3 and 3 n 3 ∕ 8 , respectively. The former is obtained by a construction, which differs from the standard diagonalization procedure, while for the upper bound the ℓ -independence number of Kneser graphs can be applied. We also establish some constructions in odd graphs K (2 k + 1 , k) , which give a lower bound for the 2-independence number of these graphs, and prove that two such constructions give the same lower bound as a previously known one. Finally, we consider the s -stable Kneser graphs K (k s + 1 , k) s − stab , derive a formula for their ℓ -independence number, and give the exact value of the independence number of the Cartesian square of K (k s + 1 , k) s − stab. [ABSTRACT FROM AUTHOR]

Abstract In 1977, Hoffman gave a characterization of graphs with smallest eigenvalue at least −2. In this paper we generalize this result to graphs with smaller smallest eigenvalue. For the proof, we use a combinatorial object named Hoffman graph, introduced by Woo and Neumaier in 1995. Our result says that for every λ ≤ − 2 , if a graph with smallest eigenvalue at least λ satisfies some local conditions, then it is highly structured. We apply our result to graphs which are cospectral with the Hamming graph H (3 , q) , the Johnson graph J (v , 3) and the 2-clique extension of grids, respectively. [ABSTRACT FROM AUTHOR]

Abstract Given a proper coloring f of a graph G , a b-vertex in f is a vertex that is adjacent to every color class but its own. It is a fall-coloring if every vertex is a b-vertex. The fall-spectrum of G is the set F (G) of all values k for which G admits a fall-coloring with k colors. These concepts were introduced by Dunbar et al., where they prove that deciding whether F (G) ≠ ∅ is NP-complete. Also, some authors have found classes of graphs G such that F (G) ⊆ { χ (G) }. We further investigate this aspect and prove that F (G) ⊆ { χ (G) } whenever G is a chordal graph, or a P 4 -sparse graph. Also, we prove that deciding whether F (G) ≠ ∅ is NP-complete if G is a chordal graph, and that deciding whether | F (G) | > 1 is NP-complete when G is a bipartite graph (deciding whether F (G) ≠ ∅ is trivial for bipartite graphs). Finally, we introduce the all-defined fall-perfect graphs and fall-perfect graphs. A graph G is all-defined fall-perfect if F (H) = { χ (H) } for every induced subgraph H of G ; and it is fall-perfect if F (H) ⊆ { χ (G) } for every induced subgraph H of G. We characterize the all-defined fall-perfect graphs, and the bipartite fall-perfect graphs. [ABSTRACT FROM AUTHOR]

A 3-connected graph G is said to be critical if for any vertex υ ∈ V (G) the graph G − υ is not 3-connected. Entringer and Slater proved that any critical 3-connected graph contains at least two vertices of degree 3. In this paper, a classification of critical 3-connected graphs with two vertices of degree 3 is given in the case where these vertices are adjacent. The case of nonadjacent vertices of degree 3 will be studied in the second part of the paper, which will be published later. [ABSTRACT FROM AUTHOR]

In the theory of spatial graphs, we state and prove an analog of the theorem on the isotopy classification of framings of classical knots. [ABSTRACT FROM AUTHOR]

Abstract Let C be the unit circle in R 2. We can view C as a plane graph whose vertices are all the points on C , and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C , where we want to place k ⩾ 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 ⩽ k ⩽ 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Θ (1 / k 2 3 ) for any k. [ABSTRACT FROM AUTHOR]

The article offers information on class of dependencies for graphs or graph entity dependencies (GEDs). Topics include the definition of a GED which is a combination of an attribute dependency and a graph pattern that could express graph functional dependencies with constant literals, the Church-Rosser property of GEDs, and the development of an independent axiom system for GEDs' finite implication.

Graph rules for the linked cluster expansion of the Legendre effective action Γ[ϕ] are derived and proven in D ≥ 2 Euclidean dimensions. A key aspect is the weight assigned to articulation vertices which is itself shown to be computable from labeled tree graphs. The hopping interaction is allowed to be long ranged and scale dependent, thereby producing an in principle exact solution of Γ[ϕ]'s functional renormalization group equation. [ABSTRACT FROM AUTHOR]

Abstract In 1975, Pippenger and Golumbic conjectured that every n -vertex graph has at most n k / (k k − k) induced cycles of length k ≥ 5. We prove that every n -vertex graph has at most 2 n k / k k induced cycles of length k. [ABSTRACT FROM AUTHOR]

We consider a family of quintic threefolds specializing to a certain reducible threefold. We describe the space of genus zero stable morphisms to the central fiber, as defined by J. Li. As an application of a straightforward extension, we prove the existence of rigid stable maps with smooth source of arbitrary genus and sufficiently high degree to very general quintics. [ABSTRACT FROM AUTHOR]

We prove that it is NP-hard to determine whether the crossing number of an input graph is even or odd. [ABSTRACT FROM AUTHOR]

We prove that every end of a graph contains either uncountably many disjoint rays or a set of disjoint rays that meet all rays of the end and start at any prescribed feasible set of start vertices. This confirms a conjecture of Georgakopoulos. [ABSTRACT FROM AUTHOR]

Abstract: Let c 1 , c 2 , … , c k be k nonnegative integers. A graph G is ( c 1 , c 2 , … , c k )‐colorable if the vertex set can be partitioned into k sets V 1 , V 2 , … , V k, such that the subgraph G [ V i ], induced by V i, has maximum degree at most c i for i = 1 , 2 , … , k. Let F denote the family of plane graphs with neither adjacent 3‐cycles nor 5‐cycles. Borodin and Raspaud (2003) conjectured that each graph in F is (0, 0, 0)‐colorable (which was disproved very recently). In this article, we prove that each graph in F is (1, 1, 0)‐colorable, which improves the results by Xu (2009) and Liu‐Li‐Yu (2016). [ABSTRACT FROM AUTHOR]

Abstract: A connected t‐chromatic graph G is double‐critical if G − { u , v } is ( t − 2 )‐colorable for each edge u v ∈ E ( G ). A long‐standing conjecture of Erdős and Lovász that the complete graphs are the only double‐critical t‐chromatic graphs remains open for all t ≥ 6. Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well‐known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double‐critical t‐chromatic graph contains a K t minor and verified their conjecture for t ≤ 7. Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K8 minor, and their proof is computer assisted. In this article, we prove that every double‐critical t‐chromatic graph contains a K t minor for all t ≤ 9. Our proof for t ≤ 8 is shorter and computer free. [ABSTRACT FROM AUTHOR]

Abstract: A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an O ( n 4 m ) time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most O ( ω 3 ) colors, where ω is the maximum number of pairwise adjacent vertices in G. [ABSTRACT FROM AUTHOR]

Abstract: Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs [1]. In the present article, we reprove their theorem using many of the same ideas, but with the key model‐theoretic ingredient of first determining the so‐called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof that implies the finite result. [ABSTRACT FROM AUTHOR]

We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth (and hence pathwidth and treewidth). The essential step is noticing the similarity to very limited string rewriting systems, whose ability to directly simulate Turing Machines is classically known. On the other hand, we show that a large class of natural reconfiguration problems (coming from graph homomorphisms) becomes tractable on graphs of bounded tree-depth, and prove a dichotomy showing this to be in some sense tight. [ABSTRACT FROM AUTHOR]

In this paper we present a simple unifying approach to prove several statements about intersecting and cross-intersecting families, including the Erdős–Ko–Rado theorem, the Hilton–Milner theorem, a theorem due to Frankl concerning the size of intersecting families with bounded maximal degree, and versions of results on the sum of sizes of non-empty cross-intersecting families due to Frankl and Tokushige. Several new stronger results are also obtained. Our approach is based on the use of regular bipartite graphs. These graphs are quite often used in Extremal Set Theory problems, however, the approach we develop proves to be particularly fruitful. [ABSTRACT FROM AUTHOR]

We prove Cadoret and Tamagawa's open image theorem for curves defined over number fields using their arguments and the machinery of Ellenberg-Hall-Kowalski employed in their paper on expander graphs. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The distance Laplacian matrix of G is defined as D L ( G ) = T r ( G ) − D ( G ) , where D ( G ) is the distance matrix and T r ( G ) = diag ( t r v 1 , t r v 2 , … , t r v n ) is the diagonal matrix of vertex transmissions of G . The largest eigenvalue of D L ( G ) is called the distance Laplacian spectral radius of G . In this paper, we obtain a graft transformation of a connected graph, which increases its distance Laplacian spectral radius. Using this transformation, we prove a conjecture involving the distance Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

A proper k -edge-coloring of a graph with colors in { 1 , 2 , … , k } is neighbor sum distinguishing (or, NSD for short) if for any two adjacent vertices, the sums of the colors of the edges incident with each of them are distinct. Flandrin et al. conjectured that every connected graph with at least 6 vertices has an NSD edge coloring with at most Δ + 2 colors. Huo et al. proved that every subcubic graph without isolated edges has an NSD 6 -edge-coloring. In this paper, we first prove a structural result about subcubic graphs by applying the decomposition theorem of Trotignon and Vušković, and then applying this structural result and the Combinatorial Nullstellensatz, we extend the NSD 6 -edge-coloring result to its list version and show that every subcubic graph without isolated edges has a list NSD 6 -edge-coloring. [ABSTRACT FROM AUTHOR]

In this note we give a proof of the Erdős-Hajnal conjecture for families of finite (hyper-)graphs without the m-order property. This theorem is in fact implicitly proved by M. Malliaris and S. Shelah (2014), however we use a new technique of independent interest combining local stability and pseudo-finite model theory. [ABSTRACT FROM AUTHOR]

We characterize a large subclass of the class of those graphs G for which the exponential domination number of H equals the domination number of H for every induced subgraph H of G. [ABSTRACT FROM AUTHOR]

For a connected graph, the first Zagreb eccentricity index ( ξ 1 ) is defined as the sum of the squares of the eccentricities of the vertices, and the second Zagreb eccentricity index ( ξ 2 ) is defined as the sum of the products of the eccentricities of pairs of adjacent vertices. We determine the n -vertex unicyclic graphs with minimum, second-minimum and third-minimum ξ 1 and ξ 2 , the n -vertex unicyclic graphs with maximum and second-maximum ξ 1 , and the n -vertex unicyclic graphs with maximum, second-maximum and third-maximum ξ 2 . [ABSTRACT FROM AUTHOR]

Let G be a ( 4 , 6 ) -fullerene graph. We show that the maximum forcing number of G is equal to its Clar number, and the maximum anti-forcing number of G is equal to its Fries number, which extend the known results for hexagonal systems with a perfect matching (Xu et al., 2013; Lei et al., 2016). Moreover, we obtain two formulas dependent only on the order of G to count the Clar number and Fries number of G respectively. Hence we can compute the maximum forcing number of a ( 4 , 6 ) -fullerene graph in linear time. This answers an open problem proposed by Afshani et al. (2004) in the case of ( 4 , 6 ) -fullerene graphs. [ABSTRACT FROM AUTHOR]

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that for any pair of adjacent vertices, the set of colors appearing on the vertex and incident edges are different. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by χ a ′ ′ ( G ) . Let G be a graph, and χ ( G ) and χ ′ ( G ) be the chromatic number and edge chromatic number of G , respectively. In this paper we show that χ a ′ ′ ( G ) ≤ χ ( G ) + χ ′ ( G ) − 1 for any graph G with χ ( G ) ≥ 6 , and χ a ′ ′ ( G ) ≤ χ ( G ) + Δ ( G ) for any graph G . Our results improve the only known upper bound 2 Δ obtained by Huang et al. (2012). As a direct consequence, we have χ a ′ ′ ( G ) ≤ Δ ( G ) + 3 if χ ( G ) = 3 and thus it implies the known results on graphs with maximum degree 3, K 4 -minor-free graphs, outerplanar graphs, graphs with maximum average degree less than 3, planar graphs with girth at least 4 and 2-degenerate graphs. [ABSTRACT FROM AUTHOR]

The Szeged index of a connected graph G is defined as S z ( G ) = ∑ e = u v ∈ E ( G ) n u ( e | G ) n v ( e | G ) , where E ( G ) is the edge set of G , and for any e = u v ∈ E ( G ) , n u ( e | G ) is the number of vertices of G lying closer to vertex u than to v , and n v ( e | G ) is the number of vertices of G lying closer to vertex v than to u . In this paper, we characterize the graph with minimum Szeged index among all the unicyclic graphs with given order and diameter. [ABSTRACT FROM AUTHOR]

This paper brings together two concepts in the theory of graph colourings: edge or total colourings distinguishing adjacent vertices and those breaking symmetries of a graph. We introduce a class of automorphisms such that edge colourings breaking them are connected to edge colouring distinguishing neighbours by multisets or sums. We call an automorphism of a graph G small if there exists a vertex of G that is mapped into its neighbour. The small distinguishing index of G , denoted D s ′ ( G ) , is the least number of colours in an edge colouring of G such that there does not exist a small automorphism of G preserving this colouring. We prove that D s ′ ( G ) ≤ 3 for every graph G without K 2 as a component, thus supporting, in a sense, the 1-2-3 Conjecture of Karoński, Łuczak and Thomason. We also consider an analogous problem for total colourings in connection with the 1-2 Conjecture of Przybyło and Woźniak. [ABSTRACT FROM AUTHOR]

To solve the state explosion problem in the reachability analysis of Petri nets, Chao recently broke the NP(nondeterministic polynomial time)-complete barrier by developing the first closed-form solution of the number of Control Related States for the kth-order system. In this paper, we propose a new proof methodology known as proof by model, which is based on the validated information of the reverse net, to simplify and accelerate the construction of the closed-form solution for Petri nets. Here, we apply this methodology to the proof procedure of Top-Right systems with one non-sharing resource placed in the top position of the right-side process. The core theoretical and data basis are that any forbidden (resp. live) state in a Petri net is non-reachable (resp. live) in its reverse net; and the validated information of the Bottom-Right system, the reverse net of Top-Right. [ABSTRACT FROM AUTHOR]

This paper deals with cooperative games in which only certain coalitions are feasible. Several combinatorial structures have been used to represent feasible coalition systems for different situations: poset of ideals, connected sets in graphs, convex geometries or antimatroids. Augmenting systems are combinatorial structures generalizing antimatroids defined in the framework of the game theory. In this paper, we introduced decreasing systems as dual structures of the augmenting systems. We connect the classical concept of dual game with the duality between these structures. The Shapley and the Banzhaf values are studied and compared for augmenting and decreasing systems. [ABSTRACT FROM PUBLISHER]

The purpose of this document is to connect two maps related to certain graphs embedded in the disc. The first is Postnikov's boundary measurement map, which combines partition functions of matchings in the graph into a map from an algebraic torus to an open positroid variety in a Grassmannian. The second is a rational map from the open positroid variety to an algebraic torus, given by certain Plücker coordinates which are expected to be a cluster in a cluster structure. This paper clarifies the relationship between these two maps, which has been ambiguous since they were introduced by Postnikov in 2001. The missing ingredient supplied by this paper is a twist automorphism of the open positroid variety, which takes the target of the boundary measurement map to the domain of the (conjectural) cluster. Among other applications, this provides an inverse to the boundary measurement map, as well as Laurent formulas for twists of Plücker coordinates. [ABSTRACT FROM AUTHOR]

Komlós conjectured in 1981 that among all graphs with minimum degree at least [ABSTRACT FROM AUTHOR]

We show that for any claw-free graph G and any graph H , γ ( G □ H ) ≥ 2 3 γ ( G ) γ ( H ) , where γ ( G ) is the domination number of G . [ABSTRACT FROM AUTHOR]