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]

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]

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]