Search

For large n we determine exactly the maximum numbers of induced C 4 and C 5 subgraphs that a planar graph on n vertices can contain. We show that K 2 , n - 2 uniquely achieves this maximum in the C 4 case, and we identify the graphs which achieve the maximum in the C 5 case. This extends work in a paper by Hakimi and Schmeichel and a paper by Ghosh, Győri, Janzer, Paulos, Salia, and Zamora which together determine both maxima asymptotically. [ABSTRACT FROM AUTHOR]

We prove that the pleated hyperbolic paraboloid, a familiar origami model known since 1927, in fact cannot be folded with the standard crease pattern in the standard mathematical model of zero-thickness paper. In contrast, we show that the model can be folded with additional creases, suggesting that real paper 'folds' into this model via small such creases. We conjecture that the circular version of this model, consisting simply of concentric circular creases, also folds without extra creases. At the heart of our results is a new structural theorem characterizing uncreased intrinsically flat surfaces-the portions of paper between the creases. Differential geometry has much to say about the local behavior of such surfaces when they are sufficiently smooth, e.g., that they are torsal ruled. But this classic result is simply false in the context of the whole surface. Our structural characterization tells the whole story, and even applies to surfaces with discontinuities in the second derivative. We use our theorem to prove fundamental properties about how paper folds, for example, that straight creases on the piece of paper must remain piecewise-straight (polygonal) by folding. [ABSTRACT FROM AUTHOR]

According to Ramsey’s Theorem, for any natural p and q there is a minimum number R(p, q) such that every graph with at least R(p, q) vertices has either a clique of size p or an independent set of size q. In the present paper, we study Ramsey numbers R(p, q) for graphs in special classes. It is known that for graphs of bounded co-chromatic number Ramsey numbers are upper-bounded by a linear function of p and q. However, the exact values of R(p, q) are known only for classes of graphs of co-chromatic number at most 2. In this paper, we determine the exact values of Ramsey numbers for classes of graphs of co-chromatic number at most 3. It is also known that for classes of graphs of unbounded splitness the value of R(p, q) is lower-bounded by (p - 1) (q - 1) + 1 . This lower bound coincides with the upper bound for perfect graphs and for all their subclasses of unbounded splitness. We call a class Ramsey-perfect if there is a constant c such that R (p , q) = (p - 1) (q - 1) + 1 for all p , q ≥ c in this class. In the present paper, we identify a number of Ramsey-perfect classes which are not subclasses of perfect graphs. [ABSTRACT FROM AUTHOR]

In this paper, we give constructions of self-orthogonal codes from orbit matrices of Deza graphs, normally regular digraphs and Deza digraphs in terms of a definition given by Wang and Feng. These constructions can also be applied to adjacency matrices of the mentioned graphs. Since a lot of constructions of Deza graphs, normally regular digraphs and Deza digraphs in the sense of Wang and Feng have been known, the methods presented in this paper give us a rich source of matrices that span self-orthogonal codes. [ABSTRACT FROM AUTHOR]

Given an edge-colored graph G c , a set of p pairs of vertices (a i , b i) together with p numbers k 1 , k 2 , … k p associated with the pairs, can we find a set of alternating paths linking the pairs (a 1 , b 1) , (a 2 , b 2) , … , in their respective numbers k 1 , k 2 , … k p ? Such is the question addressed in this paper. The problem being highly intractable, we consider a restricted version of it to edge-colored complete graphs. Even so restricted, the problem remains intractable if the paths/trails must be edge-disjoint, but it ceases to be so if the paths/trails are to be vertex-disjoint, as is proved in this paper. An approximation algorithm is presented in the end, with a performance ratio asymptotically close to 3/4 for a restricted version of the problem. [ABSTRACT FROM AUTHOR]

Let V be an n-dimensional vector space over the finite field F q and let V k q denote the family of all k-dimensional subspaces of V. A family F ⊆ V k q is called intersecting if for all F, F ′ ∈ F , we have dim (F ∩ F ′) ≥ 1. A family F ⊆ V k q is called almost intersecting if for every F ∈ F there is at most one element F ′ ∈ F satisfying dim (F ∩ F ′) = 0. In this paper we investigate almost intersecting families in the vector space V. Firstly, for large n, we determine the maximum size of an almost intersecting family in V k q , which is the same as that of an intersecting family. Secondly, we characterize the structures of all maximum almost intersecting families under the condition that they are not intersecting. [ABSTRACT FROM AUTHOR]

Let G be a graph. A bisection of G is a bipartition of V(G) with V (G) = V 1 ∪ V 2 , V 1 ∩ V 2 = ∅ and | | V 1 | - | V 2 | | ≤ 1 . Bollobás and Scott conjectured that every graph admits a bisection such that for every vertex, its external degree is greater than or equal to its internal degree minus one. In this paper, we confirm this conjecture for some regular graphs. Our results extend a result given by Ban and Linial (J Graph Theory 83:5–18, 2016). We also give an upper bound of the maximum bisection of graphs. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, the generalk-colored Gallai–Ramsey number gr k (G : H) is defined to be the minimum integer m such that every k-coloring of the complete graph on m vertices contains either a rainbow copy of G or a monochromatic copy of H. Interesting problems arise when one asks how many such rainbow copy of G and monochromatic copy of H must occur. The Gallai–Ramsey multiplicity GM k (G : H) is defined as the minimum total number of rainbow copy of G and monochromatic copy of H in any exact k-coloring of K gr k (G : H) . In this paper, we give upper and lower bounds for Gallai–Ramsey multiplicity involving some small rainbow subgraphs. [ABSTRACT FROM AUTHOR]

Given a family F of graphs, we say that a graph G is F -saturated if G does not contain any member of F , but for any edge e ∈ E (G ¯) the graph G + e does contain a member of F . The F -saturation game is played by two players starting with an empty graph and adding an edge on their turn without making a member of F . The game ends when the graph is F -saturated. One of the players wants to maximize the number edges in the final graph, while the other wants to minimize it. The game saturation number is the number of edges in the final graph given the optimal play by both players. In the present paper we study F -saturation game when F = { P 6 } consists of the single path on 6 vertices. [ABSTRACT FROM AUTHOR]

A q-graph H on n vertices is a set of vectors of length n with all entries from { 0 , 1 , ⋯ , q } and every vector (that we call a q-edge) having exactly two non-zero entries. The support of a q-edge x is the pair S x of indices of non-zero entries. We say that H is an s-copy of an ordinary graph F if | H | = | E (F) | , F is isomorphic to the graph with edge set { S x : x ∈ H } , and whenever v ∈ e , e ′ ∈ E (F) , the entries with index corresponding to v in the q-edges corresponding to e and e ′ sum up to at least s. E.g., the q-edges (1, 3, 0, 0, 0), (0, 1, 0, 0, 3), and (3, 0, 0, 0, 1) form a 4-triangle. The Turán number ex (n , F , q , s) is the maximum number of q-edges that a q-graph H on n vertices can have if it does not contain any s-copies of F. In the present paper, we determine the asymptotics of ex (n , F , q , q + 1) for many graphs F. [ABSTRACT FROM AUTHOR]

Given a graph T and a family of graphs F , the generalized Turán number of F is the maximum number of copies of T in an F -free graph on n vertices, denoted by e x (n , T , F) . A linear forest is a forest whose connected components are all paths and isolated vertices. Let L k be the family of all linear forests of size k without isolated vertices. In this paper, we obtained the maximum possible number of r-cliques in G, where G is L k -free with minimum degree at least d. Furthermore, we give a stability version of the result. As an application of the stability version of the result, we obtain a clique version of the stability of the Erdős–Gallai Theorem on matchings. [ABSTRACT FROM AUTHOR]

A vertex set in a graph is a connected set if it induces a connected subgraph. For a tree T, each subgraph induced by a connected set of T is actually a subtree of T. The number and average size of subtrees of a tree T are two well-studied parameters. Yan and Yeh developed a linear-time algorithm for computing the number of subtrees in a tree through “generating function”. In this paper, we present linear-time algorithms for computing the number and average size of connected sets in a planar 3-tree. [ABSTRACT FROM AUTHOR]

Chordal graphs are important in structural graph theory. Chordal digraphs are a digraph analogue of chordal graphs and have been a subject of active studies recently. Unlike chordal graphs, chordal digraphs lack many structural properties such as forbidden subdigraph or representation characterizations. In this paper we introduce the notion of semi-strict chordal digraphs which form a class strictly between chordal digraphs and chordal graphs. Semi-strict chordal digraphs have rich structural properties. We characterize semi-strict chordal digraphs in terms of knotting graphs, a notion analogous to the one introduced by Gallai for the study of comparability graphs. We also give forbidden subdigraph characterizations of semi-strict chordal digraphs within the classes of locally semicomplete digraphs and weakly quasi-transitive digraphs. [ABSTRACT FROM AUTHOR]

In this paper, we generalize a theorem of R. P. Stanley regarding the enumeration of paths in acyclic digraphs. [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]

The concept of book embedding, originating in computer science, has found extensive applications in various problem domains. A book embedding of a graph G involves arranging the vertices of G in an order along a line and assigning the edges to one or more half-planes. The page number of a graph is the smallest possible number of half-planes for any book embedding of the graph. Determining the page number is a key aspect of book embedding and carries significant importance. This paper aims to investigate the non-trivial lower bound of the page number for both a graph G and a random graph G ∈ G (n , p) by incorporating two seemingly unrelated concepts: edge-arboricity and Euler's Formula. Our analysis reveals that for a graph G, which is not a path, p n (G) ≥ ⌈ 1 3 a 1 (G) ⌉ , where a 1 (G) denotes the edge-arboricity of G, and for an outerplanar graph, the lower bound is optimal. For G ∈ G (n , p) , p n (G) ≥ ⌈ 1 6 n p (1 - o (1)) ⌉ with high probability, as long as c n ≤ p ≤ 3 (n - 1) 2 n log n . [ABSTRACT FROM AUTHOR]

A graph is called an edge-regular graph with parameters (n, k, a) if it is a k-regular graph with n vertices and any two adjacent vertices have a common neighbours. A quasi-strongly regular graph with parameters (n , k , a ; c 1 , c 2) , denoted by QSRG (n , k , a ; c 1 , c 2) , is an edge-regular graph with parameters (n, k, a) in which any two non-adjacent vertices have c 1 or c 2 common neighbours. A quasi-strongly regular graph is called a strictly quasi-strongly regular graph if it is neither a strongly regular graph nor a Deza graph. The purpose of our research is to complete the structural characterization of strictly QSRG (n , k , a ; k - 2 , c 2) . In an earlier paper, we characterised QSRG (n , k , a ; k - 2 , c 2) satisfying a < k - 5 and l 1 > 2 , where l 1 is the number of vertices with k - 2 common neighbours with a given vertex. In the present paper, we investigate the structural characterization of strictly QSRG (n , k , a ; k - 2 , c 2) satisfying a ≥ k - 5 . [ABSTRACT FROM AUTHOR]

Let G be a nontrivial connected and vertex-colored graph. A vertex subset X is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G - S ; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of (G - x y) - S . For a connected graph G, the rainbow vertex-disconnection number of G, rvd(G), is the minimum number of colors that are needed to make G rainbow vertex-disconnected. In this paper, we prove for any K 4 -minor free graph, r v d (G) ≤ Δ (G) and the bound is sharp. We show it is NP-complete to determine the rainbow vertex-disconnection numbers for bipartite graphs and split graphs. Moreover, we show for every ϵ > 0 , it is impossible to efficiently approximate the rainbow vertex-disconnection number of any bipartite graph and split graph within a factor of n 1 3 - ϵ unless Z P P = N P . [ABSTRACT FROM AUTHOR]

Let G be a graph. A subset D ⊆ V (G) is a decycling set of G if G - D contains no cycle. A subset D ⊆ V (G) is a cycle isolating set of G if G - N [ D ] contains no cycle. The decycling number and cycle isolation number of G, denoted by ϕ (G) and ι c (G) , are the minimum cardinalities of a decycling set and a cycle isolating set of G, respectively. Dross, Montassier and Pinlou (Discrete Appl Math 214:99–107, 2016) conjectured that if G is a planar graph of size m and girth at least g, then ϕ (G) ≤ m g . So far, this conjecture remains open. Recently, the authors proposed an analogous conjecture that if G is a connected graph of size m and girth at least g that is different from C g , then ι c (G) ≤ m + 1 g + 2 , and they presented a proof for the initial case g = 3 . In this paper, we further prove that for the cases of girth at least 4, 5 and 6, this conjecture is true. The extremal graphs of results above are characterized. [ABSTRACT FROM AUTHOR]

In this paper, we give a construction of strongly regular graphs from pseudocyclic association schemes, which is a common generalization of two constructions given by Fujisaki (2004). Furthermore, we prove that the pseudocyclic association scheme arising from the action of PGL(2, q) to the set of exterior lines in PG(2, q), called the elliptic scheme, under the assumption that q = 2 m with m an odd prime satisfies the condition of our new construction. As a consequence, we obtain a new infinite family of strongly regular graphs of Latin square type with non-prime-power number of vertices. [ABSTRACT FROM AUTHOR]

In this paper, we study the relationship between spectral radius and maximum average degree of graphs. By using this relationship and the previous technique of Li and Ning in (J Graph Theory 103:486–492, 2023), we prove that, for any given positive number ε < 1 3 , if n is a sufficiently large integer, then any graph G of order n with ρ (G) > n 2 4 contains a cycle of length t for all integers t ∈ [ 3 , (1 3 - ε) n ] , where ρ (G) is the spectral radius of G. This improves the result of Li and Ning (2023). [ABSTRACT FROM AUTHOR]

The planar Turán number of a graph H, denoted by e x P (n , H) , is the maximum number of edges in a planar graph on n vertices without containing H as a subgraph. This notion was introduced by Dowden in 2016 and has attracted quite some attention since then; those work mainly focus on finding e x P (n , H) when H is a cycle or Theta graph or H has maximum degree at least four. In this paper, we first completely determine the exact values of e x P (n , H) when H is a cubic graph. We then prove that e x P (n , 2 C 3) = ⌈ 5 n / 2 ⌉ - 5 for all n ≥ 6 , and obtain the lower bounds of e x P (n , 2 C k) for all n ≥ 2 k ≥ 8 . Finally, we also completely determine the exact values of e x P (n , K 2 , t) for all t ≥ 3 and n ≥ t + 2 . [ABSTRACT FROM AUTHOR]

The Borodin–Kostochka Conjecture states that for a graph G, if Δ (G) ≥ 9 , then χ (G) ≤ max { Δ (G) - 1 , ω (G) } . In this paper, we prove the Borodin–Kostochka Conjecture holding for odd-hole-free graphs. [ABSTRACT FROM AUTHOR]

For graphs F, G, and H, we write F → (G , H) if every red-blue coloring of the edges of F produces a red copy of G or a blue copy of H. The graph F is said to be (G, H)-minimal if it is subgraph-minimal with respect to this property. The characterization problem for Ramsey-minimal graphs is classically done for finite graphs. In 2021, Barrett and the second author generalized this problem to infinite graphs. They asked which pairs (G, H) admit a Ramsey-minimal graph and which ones do not. We show that any pair of star forests such that at least one of them involves an infinite-star component admits no Ramsey-minimal graph. Also, we construct a Ramsey-minimal graph for a finite star forest versus a subdivision graph. This paper builds upon the results of Burr et al. (Discrete Math 33:227–237, 1981) on Ramsey-minimal graphs for finite star forests. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of path planning in a weighted polygonal planar subdivision. Each polygon has an associated positive weight which shows the cost of path per unit distance of movement in that polygon. The goal is to find a minimum cost path under the Manhattan metric for two given start and destination points. First, we propose an O (n 2) time and space algorithm to solve this problem, where n is the total number of vertices in the subdivision. Then, we improve the time and space complexity of the algorithm to O (n log 2 n) and O (n log n) , respectively, by applying a divide and conquer approach. We also study the case of rectilinear regions in three dimensions and show that the minimum cost path under the Manhattan metric is obtained in O (n 2 log 3 n) time and O (n 2 log 2 n) space. [ABSTRACT FROM AUTHOR]

A compatible spanning circuit in an edge-colored graph G (not necessarily properly) is defined as a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. The existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and compatible Euler tours) has been studied extensively. Recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times in specific edge-colored graphs satisfying certain degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of such compatible s-panning circuits. We consider edge-colored graphs containing no certain forbidden induced subgraphs. As applications, we also consider the existence of such compatible spanning circuits in edge-colored graphs G with κ(G) ≥ α(G), κ(G) ≥ α(G) − 1 and κ (G) ≥ α(G), respectively. In this context, κ(G), α(G) and κ (G) denote the connectivity, the independence number and the edge connectivity of a graph G, respectively. [ABSTRACT FROM AUTHOR]

The problem of finding the minimum number of colors to color a graph properly without containing any bicolored copy of a fixed family of subgraphs has been widely studied. Most well-known examples are star coloring and acyclic coloring of graphs (Grünbaum in Isreal J Math 14(4):390–498, 1973) where bicolored copies of P 4 and cycles are not allowed, respectively. In this paper, we introduce a variation of these problems and study proper coloring of graphs not containing a bicolored path of a fixed length and provide general bounds for all graphs. A P k -coloring of an undirected graph G is a proper vertex coloring of G such that there is no bicolored copy of P k in G, and the minimum number of colors needed for a P k -coloring of G is called the P k -chromatic number of G, denoted by s k (G). We provide bounds on s k (G) for all graphs, in particular, proving that for any graph G with maximum degree d ≥ 2 , and k ≥ 4 , s k (G) ≤ ⌈ 6 10 d k - 1 k - 2 ⌉. Moreover, we find the exact values for the P k -chromatic number of the products of some cycles and paths for k = 5 , 6. [ABSTRACT FROM AUTHOR]

This paper deals with the minimum number m H (r) of edges in an H-free hypergraph with the chromatic number more than r. We show how bounds on Ramsey and Turán numbers imply bounds on m H (r) . [ABSTRACT FROM AUTHOR]

Difference systems of sets (DSSs) are combinatorial structures introduced by Levenshtein, which are a generalization of cyclic difference sets and arise in connection with code synchronization. In this paper, we describe four direct constructions of optimal DSSs from finite projective geometries and present a recursive construction of DSSs by extending the known construction. As a consequence, new infinite families of optimal DSSs can be obtained. [ABSTRACT FROM AUTHOR]

Let P 4 denote the path on four vertices. A P 4 -packing of a graph G is a collection of vertex-disjoint copies of P 4 in G. The maximum P 4 -packing problem is to find a P 4 -packing of maximum cardinality in a graph. In this paper, we prove that every simple cubic graph G on v(G) vertices has a P 4 -packing covering at least 2 v (G) 3 vertices of G and that this lower bound is sharp. Our proof provides a quadratic-time algorithm for finding such a P 4 -packing of a simple cubic graph. [ABSTRACT FROM AUTHOR]

Let [ n ] = X 1 ∪ X 2 ∪ X 3 be a partition with ⌊ n 3 ⌋ ≤ | X i | ≤ ⌈ n 3 ⌉ and define G = { G ⊂ [ n ] : | G ∩ X i | ≤ 1 , 1 ≤ i ≤ 3 } . It is easy to check that the trace G ∣ Y : = { G ∩ Y : G ∈ G } satisfies | G ∣ Y | ≤ 12 for all 4-sets Y ⊂ [ n ] . In the present paper, we prove that if F ⊂ 2 [ n ] satisfies | F | > | G | and n ≥ 28 , then | F ∣ C | ≥ 13 for some C ⊂ [ n ] , | C | = 4 . Several further results of a similar flavor are established as well. [ABSTRACT FROM AUTHOR]

Tashkinov-trees have been used as a tool for proving bounds on the chromatic index, and are becoming a fundamental tool for edge-coloring. Was its publication in a language different from English an obstacle for the accessibility of a clean and complete proof of Tashkinov’s fundamental theorem? Tashkinov’s original, Russian paper offers a clear presentation of this theorem and its proof. The theorem itself has been well understood and successfully applied, but the proof is more difficult. It builds a truly amazing recursive machine, where the various cases necessitate a refined and polished analysis to fit into one another with surprising smoothness and accuracy. The difficulties were brilliantly unknotted by the author, deserving repeated attention. The present work is the result of reading, translating, reorganizing, rewriting, completing, shortcutting and annotating Tashkinov’s proof. It is essentially the same proof, with non-negligeable communicational differences though, for instance completing it wherever it occurred to be necessary, and simplifying it whenever it appeared to be possible, at the same time trying to adapt it to the habits and taste of the international graph theory community. [ABSTRACT FROM AUTHOR]

Given a graph H and a positive integer n, the Turán number of H of the order n, denoted by ex(n, H), is the maximum size of a simple graph of order n that does not contain H as a subgraph. Given graphs G and H, G ∨ H denotes the join of G and H. In this paper, we prove e x (n , K m ∨ C 2 k - 1) = (m + 1) n 2 2 (m + 2) for n ≥ 2 (m + 2) k - 3 (m + 2) - 1 . [ABSTRACT FROM AUTHOR]

The dominating graph of a graph G is a graph whose vertices correspond to the dominating sets of G and two vertices are adjacent whenever their corresponding dominating sets differ in exactly one vertex. Studying properties of dominating graph has become an increasingly interesting subject in domination theory. On the other hand, median graphs and partial cubes are two fundamental graph classes in graph theory. In this paper, we make some new connections between domination theory and the theory of median graphs and partial cubes. As the main result, we show that the following conditions are equivalent for every graph G ≄ C 4 with no isolated vertex, and in particular, that the simple third condition completely characterizes first two ones in which three concepts of dominating graphs, median graphs and complement of minimal dominating sets get related: The dominating graph of G is a median graph, The complement of every minimal dominating set of G is a minimal dominating set, Every vertex of G is either of degree 1 or adjacent to a vertex of degree 1. As another result, we prove that the dominating graph of every graph is a partial cube and also give some examples to show that not all partial cubes or median graphs are isomorphic to the dominating graph of a graph. The above-mentioned results, as another highlight of the paper, provide novel infinite sources of examples of median graphs and partial cubes. [ABSTRACT FROM AUTHOR]

The Explorer-Director game, first introduced by Nedev and Muthukrishnan, can be described as a game where two players—Explorer and Director—determine the movement of a token that is positioned on the vertices of some given graph. At each time step, the Explorer specifies a distance that the token must move with an aim to maximize the total number of vertices ultimately visited. However, the Director adversarially chooses where to move token in an effort to minimize this number. The game ends when no new vertices can be visited. Given a graph G and a starting vertex v, the number of vertices that are visited under optimal play is denoted by f d (G , v) . In this paper, we first reduce the study of f d (G , v) to the determination of the minimum sets of vertices that are closed in a certain combinatorial sense, thus providing a structural understanding of each player’s optimal strategies. As an application, we provide some exact results as well as more general bounds when G is a square lattice or tree. In the case of trees, we also provide a complete solution even in the more restrictive setting where the strategy used by the Explorer is not allowed to depend on their opponent’s responses. In addition to this paper, a supplementary companion note will be posted to arXiv providing additional results about the game in a variety of specific graph families. [ABSTRACT FROM AUTHOR]

The Explorer-Director game, first introduced by Nedev and Muthukrishnan, can be described as a game where two players—Explorer and Director—determine the movement of a token that is positioned on the vertices of some given graph. At each time step, the Explorer specifies a distance that the token must move with an aim to maximize the total number of vertices ultimately visited. However, the Director adversarially chooses where to move token in an effort to minimize this number. The game ends when no new vertices can be visited. Given a graph G and a starting vertex v, the number of vertices that are visited under optimal play is denoted by f d (G , v) . In this paper, we first reduce the study of f d (G , v) to the determination of the minimum sets of vertices that are closed in a certain combinatorial sense, thus providing a structural understanding of each player's optimal strategies. As an application, we provide some exact results as well as more general bounds when G is a square lattice or tree. In the case of trees, we also provide a complete solution even in the more restrictive setting where the strategy used by the Explorer is not allowed to depend on their opponent's responses. In addition to this paper, a supplementary companion note will be posted to arXiv providing additional results about the game in a variety of specific graph families. [ABSTRACT FROM AUTHOR]

An odd hole is an induced odd cycle of length at least five. Let ℓ ≥ 2 be an integer, and let G ℓ denote the family of graphs which have girth 2 ℓ + 1 and have no holes of odd length at least 2 ℓ + 5 . In this paper, we prove that every graph G ∈ ∪ ℓ ≥ 3 G ℓ is 4-colourable. [ABSTRACT FROM AUTHOR]

An edge-colored graph is called rainbow if every two edges receive distinct colors, and called proper if every two adjacent edges receive distinct colors. An edge-colored graph G c is properly vertex/edge-pancyclic if every vertex/edge of the graph is contained in a proper cycle of length k for every k with 3 ≤ k ≤ | V (G) | . A triangle C of G c is called a 2-triangle if C receives exactly two colors. We call G c 2-triangle-free if G c contains no 2-triangle. Let d c (v) be the number of colors on the edges incident to v in G c and let δ c (G) be the minimum d c (v) over all the vertices v ∈ V (G c) . We show in this paper that: (i) a 2-triangle-free edge-colored complete graph K n c is properly vertex-pancyclic if δ c (K n) ≥ ⌈ n 3 ⌉ + 1 , and is properly edge-pancyclic if δ c (K n) ≥ ⌈ n 3 ⌉ + 2 . (ii) with the exception of a few edge-colored graphs on at most 9 vertices, every vertex of a 2-triangle-free edge-colored complete graph K n c with δ c (K n) ≥ 4 is contained in a rainbow C 4 ; (iii) every vertex of a 2-triangle-free edge-colored complete graph K n c with δ c (K n) ≥ 5 is contained in a rainbow C 5 unless G is proper or G is a special edge-colored K 8 . [ABSTRACT FROM AUTHOR]

DP-coloring was introduced by Dvořák and Postle as a generalization of list coloring and signed coloring. A new coloring, strictly f-degenerate transversal, is a further generalization of DP-coloring and L-forested-coloring. In this paper, we present some structural results on planar and toroidal graphs with forbidden configurations, and establish some sufficient conditions for the existence of strictly f-degenerate transversal based on these structural results. Consequently, (i) every toroidal graph without subgraphs in Fig. 2 is DP-4-colorable, and has list vertex arboricity at most 2, (ii) every toroidal graph without 4-cycles is DP-4-colorable, and has list vertex arboricity at most 2, (iii) every planar graph without subgraphs isomorphic to the configurations in Fig. 3 is DP-4-colorable, and has list vertex arboricity at most 2. These results improve upon previous results on DP-4-coloring (Kim and Ozeki in Discrete Math 341(7):1983–1986. , 2018; Sittitrai and Nakprasit in Bull Malays Math Sci Soc 43(3):2271–2285. , 2020) and (list) vertex arboricity (Choi and Zhang in Discrete Math 333:101–105. , 2014; Huang et al. in Int J Math Stat 16(1):97–105, 2015; Zhang in Iranian Math Soc 42(5):1293–1303, 2016). [ABSTRACT FROM AUTHOR]

The size Ramsey number r ^ (G , H) of two graphs G, H, introduced by Erdös et al., is defined as r ^ (G , H) = min { | E (F) | : F ⟶ (G , H) } . Recently, Gallai–Ramsey number gr k has been studied a lot. In this paper, we introduce the concept of size Gallai–Ramsey number (Simply, SGR number) of graphs. Given two graphs G and H, the size Gallai–Ramsey number gr ^ k (G : H) is defined to be the minimum integer m such that every k-coloring of the a graph on m edges contains either a rainbow copy of G or a monochromatic copy of H. We first derive some sharp upper and lower bounds of gr ^ k (G : H) . Next, we introduce two problems to compare gr k and gr ^ k and give some solutions of them. In the end, some asymptotic lower bounds for SGR number are derived by the probabilistic method and Lovász Local Lemma. [ABSTRACT FROM AUTHOR]

The perfectly matchable subgraph polytope of a graph is a (0,1)-polytope associated with the vertex sets of matchings in the graph. In this paper, we study algebraic properties (compressedness, Gorensteinness) of the toric rings of perfectly matchable subgraph polytopes. In particular, we give a complete characterization of a graph whose perfectly matchable subgraph polytope is compressed. [ABSTRACT FROM AUTHOR]

Let Γ be a connected cubic graph admitting a vertex-transitive almost simple group G of automorphisms. In this paper, we study the normality of the socle T of G in the full automorphism group Aut (Γ) of Γ . It is proved that if T is not normal in Aut (Γ) , then T = A 47 , A 23 , A 2 f - 1 with f ≥ 3 , or a simple group of Lie type of even characteristic with some exceptions. In particular, if Γ is arc-transitive and T is not normal in Aut (Γ) , then Γ is a Cayley graph on G, and (Aut (Γ) , G) = (A 48 , A 47) or (S 24 , S 23) . [ABSTRACT FROM AUTHOR]

A graph is (d 1 , … , d k) -colorable if the vertex set can be partitioned into k sets V 1 , … , V k where the maximum degree of the graph induced by V i is at most d i for each i, where 1 ≤ i ≤ k . In this paper, we prove that every planar graph without 4-cycles and 5-cycles is (3,3)-colorable, which improves the result of Sittitrai and Nakprasit, who proved that every planar graph without 4-cycles and 5-cycles is (3, 5)-colorable (Sittitrai and Nakprasit in Discrete Math 341:2142–2150, 2018). [ABSTRACT FROM AUTHOR]

For any graph G, a subset S of vertices of G is said to be a cycle isolating set of G if G - N G [ S ] contains no cycle, where N G [ S ] is the closed neighborhood of S. The cycle isolation number of G, denoted by ι c (G) , is the minimum cardinality of a cycle isolating set of G. Recently, Borg (2020) showed that if G is a connected n-vertex graph that is not isomorphic to C 3 , then ι c (G) ≤ n 4 . In this paper, we present a sharp upper bound on the cycle isolation number of a connected graph in terms of its number of edges. We prove that if G is a connected m-edge graph that is not isomorphic to C 3 , then ι c (G) ≤ m + 1 5 . Moreover, we characterize all connected graphs attaining this bound. [ABSTRACT FROM AUTHOR]

Let G be a graph. For two positive integers d and h, a (d, h)-decomposition of G is a pair (G, H) such that H is a subgraph of G of maximum degree at most h and D is an acyclic orientation of G - E (H) of maximum out-degree at most d. A graph G is (d, h)-decomposable if G has a (d, h)-decomposition. In this paper, we prove that every planar graph without intersecting 3-cycles and adjacent 4 - -cycles is (2, 1)-decomposable. As a corollary, we obtain that every planar graph without intersecting 3-cycles and adjacent 4 - -cycles has a matching M such that G - M is 2-degenerate and hence G - M is DP-3-colorable and Alon-Tarsi number of G - M is at most 3. [ABSTRACT FROM AUTHOR]

Let G be a graph, and let Q(G) and L(G) denote the signless Laplacian matrix and the Laplacian matrix of G, respectively. The polynomials ϕ (Q (G) , x) = per (x I n - Q (G)) and ϕ (L (G) , x) = per (x I n - L (G)) are called signless Laplacian permanental polynomial and Laplacian permanental polynomial of G, respectively. In this paper, we investigate the properties of roots of ϕ (Q (G) , x) . We obtain the real root distribution of ϕ (Q (G) , x) . In particular, using the Gallai–Edmonds structure theorem, we determine the structures of graphs G whose roots of signless Laplacian permanental polynomial of G contain no positive integer p, where p is the minimum vertex degree of G. And we determine completely the graphs each of which having the multiplicity of the integer root p is equal to the deficiency of a maximum p-pendant structure of the graph. These results extend the conclusion obtained by Faria (Linear Algebra Appl 299:15–35, 1995). Furthermore, we give an algorithm to calculate the multiplicity of the root p of ϕ (Q (G) , x) . And we also determine the relation between the multiplicity of the root p of ϕ (Q (G) , x) and the matching number of G. Finally, we investigate the properties of roots of Laplacian permanental polynomial of non-bipartite graphs. And some open problems are presented. [ABSTRACT FROM AUTHOR]

Kriesell (J Comb Theory Ser B 88:53–65, 2003) proposed Conjecture 1: If S ⊆ V (G) is 2k-edge-connected in a graph G, then G contains k edge-disjoint S-Steiner trees. West and Wu (J Comb Theory Ser B 102:186–205, 1961) posed Conjecture 2: If S ⊆ V (G) is 3k-edge-connected in a graph G, then G contains k edge-disjoint S-connectors, which is an analogue for S-connectors of Kriesell’s Conjecture. This paper shows If | V (G) - S | ≤ k , then Conjecture 1 is true and if | V (G) - S | ≤ 2 k , then Conjecture 2 is true. This paper also investigate the validity of two conjectures with certain additional conditions of | V (G) - S | or |S|. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. A subset S of V(G) is called a local metric generator for G if for every two adjacent vertices u and v of G there exists a vertex w ∈ S such that d G (u , w) ≠ d G (v , w) where d G (x , y) is the distance between vertices x and y in G. The local metric dimension of G, denoted by dim ℓ (G) , is the minimum cardinality among all local metric generators of G. The clique number ω (G) of G is the cardinality of a maximum set of vertices that induce a complete graph in G. The authors in [Local metric dimension for graphs with small clique numbers. Discrete Math. 345 (2022), no. 4, Paper No. 112763] conjectured that if G is a connected graph of order n with ω (G) = k where 2 ≤ k ≤ n , then dim ℓ (G) ≤ k - 1 k n . In this paper, we prove this conjecture. Furthermore, we prove that equality in this bound is satisfied if and only if G is a complete graph K n . [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of weighted chromatic polynomials of a graph associated to a weight function f of a certain degree, and discuss some of its properties. As a generalization of this concept, we define the weighted Tutte–Grothendieck polynomials of graphs. When f is harmonic, we notice that there is a correspondence between the weighted Tutte–Grothendieck polynomials of graphs and the weighted Tutte polynomials of matroids. Moreover, we present some constructions of the weighted Tutte–Grothendieck invariants for graphs as well as the weighted Tutte invariants for matroids. Finally, we give a remark on the categorification of the weighted chromatic polynomials of graphs and weighted Tutte polynomials of matroids. [ABSTRACT FROM AUTHOR]

The k-component domination number γ k (G) of G is the minimum cardinality of a dominating set S of G such that each connected component of G[S] has order at least k. Clearly, γ 1 (G) is the domination number of G and γ 2 (G) is the total domination number of G. Let G be a connected graph of size m with δ (G) ≥ 2 . Sanchis (J Graph Theory 25:139–152, 1997) proved that γ 1 (G) ≤ m + 2 3 and Henning (J Graph Theory 35:21–45, 2000) proved that γ 2 (G) ≤ m + 2 2 , respectively. In this paper, we show that if G ≇ C n of order n ≥ k + 1 ≥ 4 , then γ k (G) ≤ k m + 1 k + 2 , and this bound is sharp. [ABSTRACT FROM AUTHOR]