Search

Let F and H be two vertex disjoint graphs. The union F ∪ H is the graph with V (F ∪ H) = V (F) ∪ V (H) and E (F ∪ H) = E (F) ∪ E (H) . We use P k to denote a path on k vertices and use house to denote the complement of P 5 . In this paper, we show that if G is a ( P 3 ∪ P 2 , house)-free graph, then χ (G) ≤ 2 ω (G) . Moreover, this bound is optimal when ω (G) ≥ 2 . [ABSTRACT FROM AUTHOR]

As an analog of intersection graphs among digraphs, catch digraphs were introduced by Hiroshi Maehara in 1984. Later on, Prisner focused his research on interval catch digraphs, which he identified as diasteroidal triple free digraphs. It has been used to solve a variety of real-world challenges, such as networking, telecommunication operations, traffic control, and location problems. Oriented catch digraphs are those catch digraphs that have exactly one edge direction attached to each edge of the corresponding underlying graph. In this article, we consider two important subclasses of oriented catch digraphs, namely, oriented interval catch digraphs and oriented circular-arc catch digraphs. First, we characterize those oriented interval catch digraphs whose underlying graphs are trees in terms of forbidden subdigraphs. Next, we provide a characterization of connected proper oriented interval catch digraphs whose underlying graphs are chordal, by determining the complete list of forbidden induced subdigraphs. Another interesting result is characterizing oriented circular-arc catch digraphs, which are tournaments. [ABSTRACT FROM AUTHOR]

We determine the excluded minors characterising the class of countable graphs that embed into some compact surface. [ABSTRACT FROM AUTHOR]

In this work, we consider a combinatorial optimization problem with direct applications in blockchain mining, namely finding the most lucrative blocks for Bitcoin miners, and propose optimal algorithmic solutions. Our experiments show that our algorithms increase the miners’ revenues by more than a million dollars per month. Modern blockchains reward their miners in two ways: (i) a base reward for each block that is mined, and (ii) the transaction fees of those transactions that are included in the mined block. The base reward is fixed by the respective blockchain’s protocol and is not under the miner’s control. Hence, for a miner who wishes to maximize earnings, the fundamental problem is to form a valid block with maximal total transaction fees and then try to mine it. Moreover, in many protocols, including Bitcoin itself, the base reward halves at predetermined intervals, hence increasing the importance of maximizing transaction fees and mining an optimal block. This problem is further complicated by the fact that transactions can be prerequisites of each other or have conflicts (in case of double-spending). In this work, we consider the problem of forming an optimal block, i.e. a valid block with maximal total transaction fees, given a set of unmined transactions. On the theoretical side, we first formally model our problem as an extension of Knapsack and then show that, unlike classical Knapsack, our problem is strongly NP-hard. We also show a hardness-of-approximation result. As such, there is no hope in solving it efficiently for general instances. However, we observe that its real-world instances are quite sparse, i.e. the transactions have very few dependencies and conflicts. Using this fact, and exploiting three well-known graph sparsity parameters, namely treedepth, treewidth and pathwidth, we present exact linear-time parameterized algorithms that are applicable to the real-world instances and obtain optimal results. On the practical side, we provide an extensive experimental evaluation demonstrating that our approach vastly outperforms the current Bitcoin miners in practice, obtaining a significant per-block average increase of 11.34 percent in transaction fee revenues which amounts to almost one million dollars per month. [ABSTRACT FROM AUTHOR]

A bisection of a graph is a bipartition of its vertex set such that the number of vertices in the two parts differ by at most one, and its size is the number of edges which go across the two parts. Let G be a graph with n vertices, m edges and degree sequence d 1 , d 2 , … , d n . A celebrated result proved by Shearer shows that if G is triangle-free, then it has a bipartition of size at least m / 2 + Ω (∑ i = 1 n d i) . Lin and Zeng showed that Shearer’s lower bound holds for bisections in a graph with a perfect matching and no cycles of length 4 or 6. In this paper, we prove that if the girth of G is at least 6 and G has a perfect matching, then G has a bisection of size at least m / 2 + Ω (∑ i = 1 n d i) , which partly confirms a conjecture posed by Rao, Hou and Zeng. [ABSTRACT FROM AUTHOR]

An H-decomposition of a graph Γ is a partition of its edge set into subgraphs isomorphic to H. A transitive decomposition is a special kind of H-decomposition that is highly symmetrical in the sense that the subgraphs (copies of H) are preserved and transitively permuted by a group of automorphisms of Γ . This paper concerns transitive H-decompositions of the graph K n □ K n where H is a path. When n is an odd prime, we present a construction for a transitive path decomposition where the paths in the decomposition are considerably large compared to the number of vertices. Our main result supports well-known Gallai's conjecture and an extended version of Ringel's conjecture. [ABSTRACT FROM AUTHOR]

Given a graph H and a positive integer n, the Turán number of H for the order n, denoted by ex (n , H) , is the maximum size of a simple graph of order n not containing H as a subgraph. The book with p pages, denoted by B p , is the graph that consists of p triangles sharing a common edge. Bollobás and Erdős initiated the research on the Turán number of book graphs in 1975. The two numbers ex (p + 2 , B p) and ex (p + 3 , B p) have been determined by Qiao and Zhan. In this paper we determine the numbers ex (p + 4 , B p) , ex (p + 5 , B p) and ex (p + 6 , B p) , and characterize the corresponding extremal graphs for the numbers ex (n , B p) with n = p + 2 , p + 3 , p + 4 , p + 5. [ABSTRACT FROM AUTHOR]

For a fixed graph F, a graph G is F-saturated if G does not contain F as a subgraph, but adding any edge in E (G ¯) will result in a copy of F. The minimum size of an F-saturated graph of order n is called the saturation number of F, denoted by sat(n, F). In this paper, we are interested in saturation problem of graph K 1 ∨ P t for t ≥ 2 . As some known results, s a t (n , K 1 ∨ P t) is determined for 2 ≤ t ≤ 4 . We will show that s a t (n , K 1 ∨ P t) = (n - 1) + s a t (n - 1 , P t) for t ≥ 5 and n sufficiently large. Moreover, (K 1 ∨ P t) -saturated graphs with s a t (n , K 1 ∨ P t) edges are characterized. [ABSTRACT FROM AUTHOR]

We formulate a categorification of Robertson's conjecture analogous to the categorical graph minor conjecture of Miyata–Proudfoot–Ramos. We show that these conjectures imply the existence of a finite list of atomic graphs generating the homology of configuration spaces of graphs—in fixed degree, with a fixed number of particles, under topological embeddings. We explain how the simplest case of our conjecture follows from work of Barter and Proudfoot–Ramos, implying that the category of cographs is Noetherian, a result of potential independent interest. [ABSTRACT FROM AUTHOR]

In this paper, a new sub-family of Hypercubes called the Lucas-run graphs R n l are introduced. The name of this new family of graphs is identified with the interesting fact that | V (R n l) | is equal to the n-th Lucas number. The definition of Lucas-run graph is motivated by the Fibonacci-run graph (Eǧecioǧlu and Iršič in Discrete Appl Math 295:70–84, 2021a; in Discrete Appl Math 300:56–71, 2021b). Various interesting structural and enumerative properties of Lucas-run graphs are investigated, including the analogue of the fundamental recursion, number of vertices and edges, radius, center, diameter and medianicity. Some future research directions and open problems concerning Lucas-run graphs are also proposed. [ABSTRACT FROM AUTHOR]

A topological index is a number used in QSAR and QSPR research to assess the structural properties of a graph. The Sadhana and PI, polynomial-based topological indices, have been intensively explored in the study of chemical graph theory since a few years ago. These indices are computed using their related polynomials, however, in this study, we use an instantaneous and revolutionary approach to compute these indices for hexagonal boron nitride graphs and carbon nanotube structures. [ABSTRACT FROM AUTHOR]

Let G be a graph. We use χ(G) and ω(G) to denote the chromatic number and clique number of G respectively. A P5 is a path on 5 vertices, and an HVN is a K4 together with one more vertex which is adjacent to exactly two vertices of K4. Combining with some known result, in this paper we show that if G is (P5, HVN)-free, then χ(G) ≤ max{min{16, ω(G) + 3}, ω(G) + 1}. This upper bound is almost sharp. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity. The intersection graph of ideals of a ring R is an undirected simple graph denoted by Γ (R) whose vertices are in a one-to-one correspondence with non-zero proper ideals and two distinct vertices are joined by an edge if and only if the corresponding ideals of R have a non-zero intersection. Let M be a unitary R-module and let R ⋉ M be the idealization of M in R. In this paper, we investigate the interplay between the algebraic properties of R ⋉ M and the graph-theoretic properties of Γ (R ⋉ M) . Under some conditions on the ring R and the module M, we determine the exact form of ideals of R ⋉ M and characterize all rings R and modules M for which Γ (R ⋉ M) is a star graph. Also, we give a necessary and sufficient condition under which R ⋉ M is uniform and then we conclude that when Γ (R ⋉ M) is a complete graph. Among other results, some graph-theoretic properties of Γ (R ⋉ M) such as domination number, connectedness and grith are obtained. [ABSTRACT FROM AUTHOR]

Graph burning is a discrete time process which can be used to model the spread of social contagion. One is initially given a graph of unburned vertices. At each round (time step), one vertex is burned; unburned vertices with at least one burned neighbour from the previous round also becomes burned. The burning number of a graph is the fewest number of rounds required to burn the graph. It has been conjectured that for a graph on n vertices, the burning number is at most ⌈ n ⌉ . We show that the graph burning conjecture is true for trees without degree-2 vertices. [ABSTRACT FROM AUTHOR]

In an isolate-free graph G, a subset S of vertices is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number of G, denoted by γ t 2 (G) , is the minimum cardinality of a semitotal dominating set in G. Zhu et al. (Gr Combin 33, 1119–1130, 2017) proved that if G ∉ { K 4 , N 2 } is a connected claw-free cubic graph of order n, then γ t 2 (G) ≤ n 3 , which is sharp. They proposed the problem of characterizing the extremal graphs. We completely solve this problem. There are ten classes of graphs, three of which are infinite families of graphs. [ABSTRACT FROM AUTHOR]

The frustum model simulates network evolution by extending cliques, which represent highly interacting groups in social networks. In each time-step, new vertices are added adjacent to existing cliques of prescribed order. The model exhibits several features of social networks, such as densification, short distances, bad spectral expansion, and high local clustering. [ABSTRACT FROM AUTHOR]

A given graph H is called realizable by a graph G if G [ N (v) ] ≅ H for every vertex v of G. The Trahtenbrot–Zykov problem says that which graphs are realizable. We consider a problem somewhat opposite in a more general setting. Let t be a positive integer. We characterize all graphs G such that G - N [ v ] ∈ F for every vertex v of G, where F is the set of all t-regular graphs. Indeed, for 1 ≤ t ≤ 3 , the graphs are characterized by the same authors recently. Let t ≥ 4 . In this paper, we prove that there is no graph G such that G - N [ u ] ∈ F for each vertex u ∈ V (G) if G - N [ v ] ≅ H ∈ F for some vertex v ∈ V (G) and d i a m (H) ≥ 4 . In addition, we characterize all graphs G such that G - N [ v ] ≅ H for each v ∈ V (G) if H is one of two special graphs whose diameter are 2 and 3, respectively. [ABSTRACT FROM AUTHOR]

A very well-covered graph is a well-covered graph without isolated vertices such that the size of its minimal vertex covers is half of the number of vertices. If G is a Cohen–Macaulay very well-covered graph, we deeply investigate some algebraic properties of the cover ideal of G via the Rees algebra associated to the ideal, and especially when G is a whisker graph. [ABSTRACT FROM AUTHOR]

We present a new characterization of k-trees based on their reduced clique graphs and (k + 1) -line graphs, which are block graphs. We explore structural properties of these two classes, showing that the number of clique trees of a k-tree G equals the number of spanning trees of the (k + 1) -line graph of G. This relationship allow us to present a new approach for determining the number of spanning trees of any connected block graph and to address a special case of a “reverse problem" raised in the literature. We show that these results can be accomplished in linear time complexity. [ABSTRACT FROM AUTHOR]

The transmission of a vertex in a connected graph is the sum of its distances to all the other vertices. A graph is transmission irregular, or TI for short, when all of its vertices have mutually distinct transmissions. In an earlier paper, Al-Yakoob and Stevanović (Appl. Math. Comput. 380:125257, 2020) gave the full characterization of TI starlike trees with three branches. Here, we improve these results by using a different approach to provide the complete characterization of all TI starlike trees. Moreover, we find the precise conditions under which a double starlike tree is TI. Finally, we implement the aforementioned conditions in order to find several infinite families of TI starlike trees and TI double starlike trees. [ABSTRACT FROM AUTHOR]

Let G be a finite group with identity e and H ≠ { e } be a subgroup of G. The generalized non-coprime graph Γ G , H of G with respect to H is the simple undirected graph with G \ { e } as the vertex set and two distinct vertices x and y are adjacent if and only if gcd (| x | , | y |) ≠ 1 and either x ∈ H or y ∈ H , where |x| is the order of x ∈ G . In this paper, we study certain graph theoretical properties of generalized non-coprime graphs of finite groups, concentrating on cyclic groups. More specifically, we obtain necessary and sufficient conditions for the generalized non-coprime graph of a cyclic group to be in the class of stars, paths, triangle-free, complete bipartite, complete, split, claw-free, chordal or perfect graphs. Then we show that widening the class of groups to all finite nilpotent groups gives us no new graphs, but we give as an example of contrasting behaviour the class of EPPO groups (those in which all elements have prime power order). We conclude with a connection to the Gruenberg–Kegel graph. [ABSTRACT FROM AUTHOR]

Motivated by Berge perfect graphs, we define star-perfect graphs and characterize them. For a finite simple graph G(V, E), let [Formula: see text] denote the minimum number of induced stars contained in G such that the union of their vertex sets is V(G), and let [Formula: see text] denote the maximum number of vertices in G such that no two of them are contained in the same induced star of G. We call a graph G star-perfect if [Formula: see text], for every induced subgraph H of G. A graph G is star-perfect if and only if G is [Formula: see text]-free, for every [Formula: see text]. A bipartite graph G is star-perfect if and only if every induced cycle in G is of length [Formula: see text]. The minimum parameter [Formula: see text] and the maximum parameter [Formula: see text] have been extensively studied in various contexts.

The class of [Formula: see text]-free graphs has been well studied in the past. In the paper “On the chromatic number of [Formula: see text]-free graphs, Discrete Applied Mathematics, 253 (2019), 14–24”, it was shown that the class of [Formula: see text]-free graphs and [Formula: see text]-free graphs admit a linear χ-binding function. In this paper, we study some subclasses of [Formula: see text]-free graphs which is a superclass of [Formula: see text]-free graphs. We show that [Formula: see text]-free graphs and [Formula: see text]-free graphs also admit linear χ-binding functions. In addition, we give a tight χ-binding function for [Formula: see text]-free graphs and improve the χ-bound for [Formula: see text]-free graphs with ω = 4.

Fiol has characterized quotient-polynomial graphs as precisely the connected graphs whose adjacency matrix generates the adjacency algebra of a symmetric association scheme. We show that a collection of non-negative integer parameters of size d + d (d - 1) 2 is adequate for describing symmetric association schemes of class d that are generated by the adjacency matrix of their first non-trivial relation. We use this to generate a database of the corresponding quotient-polynomial graphs that have small valency and up to 6 classes, and among these find new feasible parameter sets for symmetric association schemes with noncyclotomic eigenvalues. [ABSTRACT FROM AUTHOR]

Given a 3-hypergraph H, a subset M of V(H) is a module of H if for each e ∈ E (H) such that e ∩ M ≠ ∅ and e \ M ≠ ∅ , there exists m ∈ M such that e ∩ M = { m } and for every n ∈ M , we have (e \ { m }) ∪ { n } ∈ E (H) . For example, ∅ , V(H) and { v } , where v ∈ V (H) , are modules of H, called trivial. A 3-hypergraph is prime if all its modules are trivial. Furthermore, a prime 3-hypergraph is critical if all its induced subhypergraphs, obtained by removing one vertex, are not prime. Lastly, we associate with a prime 3-hypergraph its primality graph the edges of which are the unordered pairs of vertices whose removal provides a prime induced subhypergraph. We characterize the critical 3-hypergraphs together with their primality graph. [ABSTRACT FROM AUTHOR]

It is known that every hereditary property can be characterized by finitely many minimal obstructions when restricted to either the class of cographs or the class of P 4 -reducible graphs. In this work, we prove that the same is true when restricted to some other superclasses of cographs, including P 4 -sparse and P 4 -extendible graphs (both of which extend P 4 -reducible graphs). We also present complete lists of P 4 -sparse and P 4 -extendible minimal obstructions for polarity, monopolarity, unipolarity, and (s, 1)-polarity, where s is a positive integer. In parallel to the case of P 4 -reducible graphs, all the P 4 -sparse minimal obstructions for these hereditary properties are cographs. [ABSTRACT FROM AUTHOR]

Galinier, Habib, and Paul introduced the reduced clique graph of a chordal graph G. The nodes of the reduced clique graph are the maximal cliques of G, and two nodes are joined by an edge if and only if they form a non-disjoint separating pair of cliques in G. In this case the weight of the edge is the size of the intersection of the two cliques. A clique tree of G is a tree with the maximal cliques of G as its nodes, where for any v ∈ V (G) , the subgraph induced by the nodes containing v is connected. Galinier et al. prove that a spanning tree of the reduced clique graph is a clique tree if and only if it has maximum weight, but their proof contains an error. We explain and correct this error. In addition, we initiate a study of the structure of reduced clique graphs by proving that they cannot contain any induced cycle of length five (although they may contain induced cycles of length three or any even integer greater than two). We show that no cycle of length four or more is isomorphic to a reduced clique graph. We prove that the class of clique graphs of chordal graphs is not comparable to the class of reduced clique graphs of chordal graphs by providing examples that are in each of these classes without being in the other. [ABSTRACT FROM AUTHOR]

HHD-free is the class of graphs which contain no house, hole, or domino as induced subgraph. It is known that HHD-free graphs can be characterized via LexBFS-ordering and via m 3 -convexity. In this paper we present new characterizations of HHD-free via domination of paths and walks. To achieve this, in particular we concentrate our attention on m 3 path, i.e, an induced path of length at least 3 between two non-adjacent vertices in a graph G. We show that the domination between induced paths, paths and walks versus m 3 paths, gives rise to characterization of HHD-free. We also characterize the class of graphs in which every m 3 path dominates every path, induced path, walk, and m 3 path, respectively. [ABSTRACT FROM AUTHOR]

Consider a bipartite distance-regularized graph Γ with color partitions Y and Y ′ . Notably, all vertices in partition Y (and similarly in Y ′ ) exhibit a shared eccentricity denoted as D (and D ′ , respectively). The characterization of bipartite distance-regularized graphs, specifically those with D ≤ 3 , in relation to the incidence structures they represent is well established. However, when D = 4 , there are only two possible scenarios: either D ′ = 3 or D ′ = 4 . The instance where D = 4 and D ′ = 3 has been previously investigated. In this paper, we establish a one-to-one correspondence between the incidence graphs of quasi-symmetric SPBIBDs with parameters (v , b , r , k , λ 1 , 0) of type (k - 1 , t) , featuring intersection numbers x = 0 and y > 0 (where y ≤ t < k ), and bipartite distance-regularized graphs with D = D ′ = 4 . Moreover, our investigations result in the systematic classification of 2-Y-homogeneous bipartite distance-regularized graphs, which are incidence graphs of quasi-symmetric SPBIBDs with parameters (v , b , r , k , λ 1 , 0) of type (k - 1 , t) with intersection numbers x = 0 and y = 1 . [ABSTRACT FROM AUTHOR]