Search

Let G be a graph and k a positive integer. A strong k-edge-coloring of G is a mapping ϕ : E (G) → { 1 , 2 , ⋯ , k } such that for any two edges e and e ′ that are either adjacent to each other or adjacent to a common edge, ϕ (e) ≠ ϕ (e ′) . The strong chromatic index of G, denoted as χ s ′ (G) , is the minimum integer k such that G has a strong k-edge-coloring. Lv, Li and Zhang [Graphs and Combinatorics 38 (3) (2022) 63] proved that if G is a claw-free subcubic graph other than the triangular prism then χ s ′ (G) ≤ 8 . In addition, they asked if the upper bound 8 can be improved to 7. In this paper, we answer this question in the affirmative. Our proof implies a polynomial-time algorithm for finding strong 7-edge-colorings of such graphs. We also construct infinitely many claw-free subcubic graphs with their strong chromatic indices attaining the bound 7. [ABSTRACT FROM AUTHOR]

A noncrossing forest is a forest drawn on n points numbered in counterclockwise order on a circle in such a way that its edges are rectilinear and do not cross. Utilizing analytic combinatorics, Flajolet and Noy obtained the number of noncrossing forests with n vertices and k components. In this paper, we will give a new representation for noncrossing forests. Based on such respresentation, we establish a decomposition algorithm and a merging algorithm, which leads to a bijection between labeled noncrossing forests and sets of rooted matches. As an application, we derive a new formula, which is a refinement of the formula given by Flajolet and Noy. [ABSTRACT FROM AUTHOR]

Let D be a strong balanced bipartite digraph on 2a vertices. For x , y , z ∈ V (D) , if x → z and y → z , then we call the pair { x , y } dominating; if z → x and z → y , then we call the pair { x , y } dominated. In 2017, Adamus [Graphs and Combinatorics, 33(2017) 43–51] proved that if d (x) + d (y) ≥ 3 a whenever { x , y } is a dominating or dominated pair, then D is Hamiltonian. In 2021, Adamus [Discrete Mathematics, 344(3) (2021) 112240] proved that if only every dominating pair of vertices { x , y } in D satisfies d (x) + d (y) ≥ 3 a + 1 , then D is Hamiltonian. In this paper, we show that the same conclusion is reached if we replace 3 a + 1 with 3a in the above condition. The lower bound for 3a is sharp. [ABSTRACT FROM AUTHOR]

In this paper, we study factorizations of cycles. The main result is that under certain condition, the number of ways to factor a d-cycle into a product of cycles of prescribed lengths is d. To prove our result, we first define a new class of combinatorial objects, multi-noded rooted trees, which generalize rooted trees. We find the cardinality of this new class which with proper parameters is exactly d. The main part of this paper is the proof that there is a bijection from factorizations of a d-cycle to multi-noded rooted trees via factorization graphs. This implies the desired formula. The factorization problem we consider has its origin in geometry, and is related to the study of a special family of Hurwitz numbers: pure-cycle Hurwitz numbers. Via the standard translation of Hurwitz numbers into group theory, our main result is equivalent to the following: when the genus is 0 and one of the ramification indices is d, the degree of the covers, the pure-cycle Hurwitz number is d, where r is the number of branch points. [ABSTRACT FROM AUTHOR]

Let $$G=(V,E)$$ be a graph and $$\phi :V\cup E\rightarrow \{1,2,\ldots ,k\}$$ be a total coloring of G. Let C( v) denote the set of the color of vertex v and the colors of the edges incident with v. Let f( v) denote the sum of the color of vertex v and the colors of the edges incident with v. The total coloring $$\phi $$ is called neighbor set distinguishing or adjacent vertex distinguishing if $$C(u)\ne C(v)$$ for each edge $$uv\in E(G)$$ . We say that $$\phi $$ is neighbor sum distinguishing if $$f(u)\ne f(v)$$ for each edge $$uv\in E(G)$$ . In both problems the challenging conjectures presume that such colorings exist for any graph G if $$k\ge \varDelta (G)+3$$ . In this paper, by using the famous Combinatorial Nullstellensatz, we prove that in both problems $$k\ge \varDelta (G)+2\mathrm{col}(G)-2$$ is sufficient, moreover we prove that if G is not a forest and $$\varDelta \ge 4$$ , then $$k\ge \varDelta (G)+2\mathrm{col}(G)-3$$ is sufficient, where $$\mathrm{col}(G)$$ is the coloring number of G. In fact we prove these results in their list versions, which improve the previous results. As a consequence, we obtain an upper bound of the form $$\varDelta (G)+C$$ for some families of graphs, e.g. $$\varDelta +9$$ for planar graphs. In particular, we therefore obtain that when $$\varDelta \ge 4$$ two conjectures we mentioned above hold for 2-degenerate graphs (with coloring number at most 3) in their list versions. [ABSTRACT FROM AUTHOR]

The concept of splitting-balanced block designs (SBD) was defined with some applications for authentication codes by Ogata, Kurosawa, Stinson and Saido. The existence of SBDs has been discussed through direct and recursive constructions in literature. In this paper, we focus on the property of resolvability in a SBD, and two improved bounds for the number of blocks in SBDs with resolvability are presented. Furthermore, some equivalence between SBDs with resolvability and other combinatorial designs are provided. Finally existence results of some classes of SBDs with resolvability are shown by use of recursive constructions and available results on other combinatorial structures. [ABSTRACT FROM AUTHOR]

The subdivision graph S( Σ) of a connected graph Σ is constructed by adding a vertex in the middle of each edge. In a previous paper written with Cheryl E. Praeger, we characterised the graphs Σ such that S( Σ) is locally ( G, s)-distance transitive for s ≤ 2 diam( Σ) − 1 and some G ≤ Aut( Σ). In this paper, we solve the remaining cases by classifying all the graphs Σ such that S( Σ) is locally ( G, s)-distance transitive for some s ≥ 2 diam( Σ) and some G ≤ Aut( Σ). As a corollary, we get a classification of all the graphs whose subdivision graph is locally distance transitive. [ABSTRACT FROM AUTHOR]

Hua et al. (Discrete Math 311, 2259-2267, 2011) and Yang et al. (Discrete Math. 339, 522-532, 2016) classify arc-transitive pentavalent graphs of order 2 pq and of order 2 pqr (with p, q, r distinct odd primes), respectively. In this paper, we extend their results by giving a classification of arc-transitive pentavalent graphs of any square-free order. [ABSTRACT FROM AUTHOR]

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. An open problem concerning clique-perfect graphs is to find all minimal forbidden induced subgraphs of clique-perfect graphs. In this paper we characterize the clique-perfectness of claw-free planar graphs by forbidden induced subgraphs. Furthermore, we also characterize the clique-perfectness of claw-free graphs with degree at most 4 and graphs with degree at most 3. As an immediate corollary, we show that claw-free cubic graphs are clique-perfect. [ABSTRACT FROM AUTHOR]

Two resolutions of the same 3-design are said to be orthogonal when each parallel class of one resolution has at most one block in common with each parallel class of the other resolution. If an H design has two orthogonal resolutions, then the H design is called a doubly resolvable H design. In this paper, we construct two infinite classes of doubly resolvable H( n, g, 4, 3)s for $$n=6$$ or 8 and use a quadrupling construction to obtain more infinite classes of doubly resolvable H designs. [ABSTRACT FROM AUTHOR]

In this paper we study the resonance variety of a line combinatorics. We introduce the concept of combinatorial pencil, which characterizes the components of this variety and their dimensions. The main theorem in this paper states that there is a correspondence between components of the resonance variety and combinatorial pencils. As a consequence, we conclude that the depth of a component of the resonance variety is determined by its dimension; and that there are no embedded components. This result is useful to study the isomorphisms between fundamental groups of the complements of line arrangements with the same combinatorial type. The definition of combinatorial pencil generalizes the idea of net given by Yuzvinsky and others. [ABSTRACT FROM AUTHOR]

A real number α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that for any ∈ > 0 and any integer m ≥ r, there exists an integer n0 such that any r-uniform graph with n > n0 vertices and density ≥ α + ∈ contains a subgraph with m vertices and density ≥ α + c. It follows from a fundamental theorem of Erdös and Stone that every α ∈ [0, 1) is a jump for r = 2. Erdös also showed that every number in [0, r!/ r r) is a jump for r ≥ 3 and asked whether every number in [0, 1) is a jump for r ≥ 3 as well. Frankl and Rödl gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. Recently, more non-jumps were found for some r ≥ 3. But there are still a lot of unknowns on determining which numbers are jumps for r ≥ 3. The set of all previous known non-jumps for r = 3 has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every r ≥ 3. It generalizes the main result in the paper ‘A note on the jumping constant conjecture of Erdös’ by Frankl, Peng, Rödl and Talbot published in the Journal of Combinatorial Theory Ser. B. 97 (2007), 204–216. [ABSTRACT FROM AUTHOR]

The Hadwiger number η( G) of a graph G is the largest integer n for which the complete graph K n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η( G) ≥ χ( G), where χ( G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product $$G \square H$$ of graphs. As the main result of this paper, we prove that $$\eta (G_1 \square G_2) \ge h\sqrt{l}\left (1 - o(1) \right )$$ for any two graphs G 1 and G 2 with η( G 1) = h and η( G 2) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following: [ABSTRACT FROM AUTHOR]

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr( K m □ P n ), the crossing number of the Cartesian product K m □ P n . We prove that $$cr(K_{m} \square P_n)\leq \frac{1}{4}\lfloor\frac{m+1}{2}\rfloor\lfloor\frac{m-1}{2} \rfloor\lfloor\frac{m-2}{2}\rfloor(n\lfloor\frac{m+4}{2} \rfloor+ \lfloor\frac{m-4}{2}\rfloor)$$ for m ≥ 3, n ≥ 1 and cr( K m □ P n )≥ ( n − 1) cr( K m+2 − e) + 2 cr( K m+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr( K 6 □ P n ) = 15 n + 3. [ABSTRACT FROM AUTHOR]

Consider anm×nzero-one matrixA. Ans×tsubmatrix ofAis said to beevenif the sum of its entries is even. In this paper, we focus on the casem=nands=t=2. ThemaximumnumberM(n) of even 2×2 submatrices ofAis clearlyand corresponds to the matrixAhaving, e.g., all ones (or zeros). A more interesting question, motivated by Turán numbers and Hadamard matrices, is that of theminimumnumberm(n) of such matrices. It has recently been shown thatfor some constantB. In this paper we show that if the matrixA=A n is considered to be induced by an infinite zero one matrix obtained at random, thenwhereE n denotes the number of even 2×2 submatrices ofA n. Results such as these provide us with specific information about the tightness of the concentration ofE n around its expected value of [ABSTRACT FROM AUTHOR]

The notion of augmenting graphs generalizes Berge's idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) problem. Recently, the augmenting graph approach has been successfully applied to solve MIS in various other special cases. However, our knowledge of augmenting graphs is still very limited and we do not even know what the minimal infinite classes of augmenting graphs are. In the present paper, we find an answer to this question and apply it to extend the area of polynomial-time solvability of the maximum independent set problem. [ABSTRACT FROM AUTHOR]

We classify all possible zero-divisor graphs of a particular family of quotients of $$\mathbf{Z}_4[x,y,w,z]$$ . As the 90 quotients vary, we obtain a total of 7 graphs, corresponding to seven isomorphism classes, and one of these graphs provides a new example which contradicts Beck's conjecture on the chromatic number of a zero-divisor graph. The algebraic analysis is strongly supported by the combinatorial setting, as already shown in a previous paper, where the graph-theoretical tools were presented and successfully applied to $$\mathbf{Z}_4[x,y,z]$$ -therefore, the just smaller case-in order to get a deeper knowledge of the classical counterexample to Beck's conjecture. [ABSTRACT FROM AUTHOR]

It has long been conjectured that the total chromatic number $$ \chi ^{\prime \prime }(K)$$ of the complete $$p$$ -partite graph $$K = K(r_1, \dots , r_p)$$ is $$\Delta (K) + 1$$ if and only if both $$K \ne K_{r,r}$$ and $$|V(K)| \equiv $$ 0 (mod 2) implies that $$\Sigma _{v \in V(K)}(\Delta (K) - d_K(v))$$ is at least the number of parts of odd size. It is known that $$\chi ^{\prime \prime }(K) \le \Delta (K) + 2$$ . In this paper, a new approach is introduced to attack the conjecture that makes use of amalgamations of graphs. The power of this approach is demonstrated by settling the conjecture for all complete 5-partite graphs. [ABSTRACT FROM AUTHOR]

Difference systems of sets (DSS) are combinatorial structures introduced by Levenshtein in (Probl Peredachi Inform 7(3):215-222, ), which are a generalization of cyclic difference sets and arise in connection with code synchronization. In this paper, we consider a collection of pairs in a finite field of a prime order $$p=ef+1$$ to be a regular DSS with parameters $$(p,2,f,\rho )$$ . We give a lower bound on the parameter $$\rho $$ using cyclotomic numbers for $$e=3$$ and 4. In addition, we present a condition for which the collection of pairs forms an optimal DSS for $$e=4$$ . [ABSTRACT FROM AUTHOR]

In this paper, some constructions of Yang Hui type magic squares are provided. As their application, it is shown that there exists a Yang Hui type magic square YMS $$(n,2)$$ for all even order $$n\ge 4$$ . Meanwhile, a diagonally ordered irrational YMS $$(n,2)$$ is also mentioned and it is shown that such a YMS $$(n,2)$$ exists for all integers $$n\equiv 2\pmod 4$$ with $$n\ge 6$$ . [ABSTRACT FROM AUTHOR]

Let $$P$$ be a set of $$n$$ points in the plane. A geometric graph $$G$$ on $$P$$ is said to be locally Gabriel if for every edge $$(u,v)$$ in $$G$$ , the Euclidean disk with the segment joining $$u$$ and $$v$$ as diameter does not contain any points of $$P$$ that are neighbors of $$u$$ or $$v$$ in $$G$$ . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any $$n$$ , there exists LGG with $$\Omega (n^{5/4})$$ edges. This improves upon the previous best bound of $$\Omega (n^{1+\frac{1}{\log \log n}})$$ . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any $$n$$ point set, there exists an independent set of size $$\Omega (\sqrt{n}\log n)$$ . [ABSTRACT FROM AUTHOR]

It is conjectured Zhang et al. (Appl Math Lett 15: 623-626, ) that if $$G\notin \{K_2,C_5\}$$ is a connected graph, then there is a proper edge coloring of $$G$$ using at most $$\Delta (G)+2$$ colors that distinguishes vertices of $$G$$ by means of their (naturally defined) color sets. In the paper several results concerning edge colorings of the direct product of two graphs are obtained that support the conjecture. [ABSTRACT FROM AUTHOR]

Chvátal and Erdős proved a well-known result that the graph $$G$$ with connectivity $$\kappa (G)$$ not less than its independence number $$\alpha (G)$$ [ $$\alpha (G)+1$$ , $$\alpha (G)-1$$ , respectively] is Hamiltonian (traceable, Hamiltonian-connected, respectively). In this paper, we strengthen the Chvátal-Erdős theorem to the following: Let $$G$$ be a simple 2-connected graph of order large enough such that $$\alpha (G)\le \kappa (G)+1$$ [ $$\alpha (G)\le \kappa (G)+2$$ , $$\alpha (G)\le \kappa (G),$$ respectively] and such that the number of maximum independent sets of cardinality $$\kappa (G)+1$$ [ $$\kappa (G)+2$$ , $$\kappa (G)$$ , respectively] is at most $$n-2\kappa (G)$$ [ $$n-2\kappa (G)-1$$ , $$n-2\kappa (G)+1$$ , respectively]. Then $$G$$ is either Hamiltonian (traceable, Hamiltonian-connected, respectively) or a subgraph of $$K_{k}+((kK_1)\cup K_{n-2k})$$ [ $$K_{k}+((k+1)K_1\cup K_{n-2k-1})$$ , $$K_{k}+((k-1)K_1\cup K_{n-2k+1})$$ , respectively]. [ABSTRACT FROM AUTHOR]

We discuss the existence of vertex disjoint path coverings with prescribed ends for the $$n$$ -dimensional hypercube with or without deleted vertices. Depending on the type of the set of deleted vertices and desired properties of the path coverings we establish the minimal integer $$m$$ such that for every $$n \ge m$$ such path coverings exist. Using some of these results, for $$k \le 4$$ , we prove Locke's conjecture that a hypercube with $$k$$ deleted vertices of each parity is Hamiltonian if $$n \ge k +2.$$ Some of our lemmas substantially generalize known results of I. Havel and T. Dvořák. At the end of the paper we formulate some conjectures supported by our results. [ABSTRACT FROM AUTHOR]

A function $$f:V(G)\rightarrow \{0,1,2\}$$ on graph $$G=(V(G),E(G))$$ satisfying the condition that every vertex $$u$$ for which $$f(u)=0$$ is adjacent at least one vertex $$v$$ for which $$f(v)=2$$ is a Roman dominating function (RDF). The weight of an RDF is the sum of its function value over all vertices. The Roman domination number of $$G$$ , denoted by $$\gamma _{R}(G)$$ , is the minimum weight of an RDF on $$G$$ . An RDF $$f:V(G)\rightarrow \{0,1,2\}$$ is called a global Roman dominating function (GRDF) if $$f$$ is also an RDF of the complement $$\overline{G}$$ of $$G$$ . The global Roman domination number of $$G$$ , denoted by $$\gamma _{gR}(G)$$ , is the minimum weight of a GRDF on $$G$$ . In this paper, we initiate global Roman domination number and study the basic properties of global Roman domination of a graph. Then we present some sharp bounds for global Roman domination number. In particular, we prove that for any tree of order $$n\ge 4$$ , $$\gamma _{gR}(T)\le \gamma _{R}(T)+2$$ and we characterize all trees with $$\gamma _{gR}(T)=\gamma _{R}(T)+2$$ and $$\gamma _{gR}(T)= \gamma _{R}(T)+1$$ . [ABSTRACT FROM AUTHOR]

Let $$G$$ be a graph. The core of $$G$$ , denoted by $$G_{\Delta }$$ , is the subgraph of $$G$$ induced by the vertices of degree $$\Delta (G)$$ , where $$\Delta (G)$$ denotes the maximum degree of $$G$$ . A $$k$$ -edge coloring of $$G$$ is a function $$f:E(G)\rightarrow L$$ such that $$|L| = k$$ and $$f(e_1)\ne f(e_2)$$ , for any two adjacent edges $$e_1$$ and $$e_2$$ of $$G$$ . The chromatic index of $$G$$ , denoted by $$\chi '(G)$$ , is the minimum number $$k$$ for which $$G$$ has a $$k$$ -edge coloring. A graph $$G$$ is said to be Class $$1$$ if $$\chi '(G) = \Delta (G)$$ and Class $$2$$ if $$\chi '(G) = \Delta (G) + 1$$ . Hilton and Zhao conjectured that if $$G$$ is a connected graph, $$\Delta (G_{\Delta })\le 2$$ , and $$G$$ is not the Petersen graph with one vertex removed, then $$G$$ is Class $$2$$ if and only if $$G$$ is overfull. In this paper, we prove this conjecture for claw-free graphs of even order. [ABSTRACT FROM AUTHOR]

A graph $$G$$ is edge- $$L$$ -colorable if for a given edge assignment $$L=\{L(e):e\in E(G)\}$$ , there exits a proper edge-coloring $$\phi $$ of $$G$$ such that $$\phi (e)\in L(e)$$ for all $$e\in E(G)$$ . If $$G$$ is edge- $$L$$ -colorable for every edge assignment $$L$$ with $$| L(e)|\ge k$$ for $$e\in E(G)$$ , then $$G$$ is said to be edge- $$k$$ -choosable. In this paper, we prove that if $$G$$ is a planar graph without non-induced $$6$$ -cycles, then $$G$$ is edge- $$k$$ -choosable, where $$k=\max \{8, \Delta (G)+1\}$$ . [ABSTRACT FROM AUTHOR]

A partial order relation in the set $$\mathcal {G}(n,k)$$ of graphs of order $$n$$ and chromatic number $$k$$ can be defined as follows: Let $$G$$ and $$H$$ be two graphs in $$\mathcal {G}(n,k)$$ . $$G$$ is said to be less than $$H$$ if $$c_i(G)\le c_i(H)$$ holds for every $$i$$ , $$k\le i\le n$$ and at least one inequality is strict, where $$c_i(G)$$ denotes the number of $$i$$ -color partitions of $$G$$ . These numbers are the coefficients of the chromatic polynomial in factorial form. In (J Graph Theory 43:210-222, ) the first $$\lceil n/2\rceil $$ levels of the diagram of the partially ordered set of connected 3-chromatic graphs of order $$n$$ were described. In this paper the previous work is continued and a description of the $$(\lceil n/2\rceil +1)$$ -st level is given; it contains $$n/2+1$$ bicyclic graphs for even $$n$$ and $$(n-1)/2$$ bicyclic graphs for odd $$n$$ . Some consequences concerning ordering chromatic polynomials of these graphs are deduced. [ABSTRACT FROM AUTHOR]

A graph is said to be $$C_k$$ -saturated if it contains no cycles of length $$k$$ but does contain such a cycle after the addition of any edge from the complement of the graph. Determining the minimum size of $$C_k$$ -saturated graphs is one of the interesting problems on extremal graphs. The exact minimum sizes are known for $$k=3, 4$$ and $$5$$ , but only general bounds are shown for $$k \ge 6$$ . This paper deals with bounds of the minimum size when $$k=6$$ . It is shown that the minimum size of a $$C_6$$ -saturated graph on $$n$$ vertices is at least $$ \lceil \frac{7n}{6}\rceil -2$$ and at most $$ \lfloor \frac{3n-3}{2} \rfloor $$ . This lower bound improves the best previously known result. [ABSTRACT FROM AUTHOR]

A digraph $$D$$ is said to be an $$m$$ -coloured digraph if its arcs are coloured with $$m$$ colors. A directed path is called monochromatic if all of its arcs are coloured alike. A set $$N \subseteq $$ V ( $$D$$ ) of vertices of $$D$$ is said to be a kernel by monochromatic paths of the $$m$$ -coloured digraph $$D$$ if it satisfies the two following properties : (1) for any two different vertices $$x$$ , $$y$$ $$\in $$ N there is no monochromatic directed path between them, and (2) for each vertex $$u$$ $$\in $$ V( $$D$$ ) $$\setminus N$$ there exists a $$uv$$ -monochromatic directed path, for some $$v$$ $$\in N$$ . Let $$D$$ be an arc-coloured digraph. In 2009 Galeana-Sánchez introduced the concept of color-class digraph of $$D$$ , denoted by $$\fancyscript{C}_C$$ ( $$D$$ ), as follows: the vertices of the color-class digraph are the colors represented in the arcs of $$D$$ , and ( $$i$$ , $$j$$ ) $$\in $$ $$A$$ ( $$\fancyscript{C}_C$$ ( $$D$$ )) if and only if there exist two arcs namely ( $$u$$ , $$v$$ ) and ( $$v$$ , $$w$$ ) in $$D$$ such that ( $$u$$ , $$v$$ ) has color $$i$$ and ( $$v$$ , $$w$$ ) has color $$j$$ . Galeana-Sánchez introduced the concept of color-class digraph mainly to prove that if $$D$$ is a fnite arc-coloured digraph such that $$\fancyscript{C}_C$$ ( $$D$$ ) is a bipartite digraph, then D has a kernel by monochromatic paths. In this paper we will see some results related to the above result, which show the existence of kernels by monochromatic paths in arc-coloured digraphs. In particular, we will prove the following generalization of the previous result: Let $$D$$ be an $$m$$ -coloured digraph and $$\fancyscript{C}_C$$ ( $$D$$ ) its color-class digraph. If $$\fancyscript{C}_C$$ ( $$D$$ ) has no cycles of odd length at least 3, then $$D$$ has a kernel by monochromatic paths. Finally we will prove Richardson's Theorem as a direct consequence of the previous result. [ABSTRACT FROM AUTHOR]

Given a number $$P$$ , we study the following three isoperimetric problems introduced by Besicovitch in 1952: (1) Let $$S$$ be a set of $$n$$ points in the plane. Among all the curves with perimeter $$P$$ that enclose $$S$$ , what is the curve that encloses the maximum area? (2) Let $$Q$$ be a convex polygon with $$n$$ vertices. Among all the curves with perimeter $$P$$ contained in $$Q$$ , what is the curve that encloses the maximum area? (3) Let $$r_{\circ }$$ be a positive number. Among all the curves with perimeter $$P$$ and circumradius $$r_{\circ }$$ , what is the curve that encloses the maximum area? In this paper, we provide a complete characterization for the solutions to Problems 1, 2 and 3. We show that there are cases where the solution to Problem 1 cannot be computed exactly. However, it is possible to compute in $$O(n \log n)$$ time the exact combinatorial structure of the solution. In addition, we show how to compute an approximation of this solution with arbitrary precision. For Problem 2, we provide an $$O(n\log n)$$ -time algorithm to compute its solution exactly. In the case of Problem 3, we show that the problem can be solved in constant time. As a side note, we show that if $$S$$ is a set of $$n$$ points in the plane, then finding the area of the curve of perimeter $$P$$ that encloses $$S$$ and has minimum area is NP-hard. [ABSTRACT FROM AUTHOR]

An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it belongs to a cycle of length l for all 3 ≤ l ≤ n. We call a vertex u of T an out-pancyclic vertex of T, if each out-arc of u is pancyclic in T. Yao et al. (Discrete Appl. Math. 99, 245-249, ) proved that every strong tournament contains an out-pancyclic vertex. For strong tournaments with minimum out-degree 1, Yao et al. found an infinite class of strong tournaments, each of which contains exactly one out-pancyclic vertex. In this paper, we prove that every strong tournament with minimum out-degree at least 2 contains three out-pancyclic vertices. Our result is best possible since there is an infinite family of strong tournaments with minimum degree at least 2 and no more than 3 out-pancyclic vertices. [ABSTRACT FROM AUTHOR]

A graph Γ is called half-arc-transitive if it's automorphism group Aut Γ is transitive on the vertex set and edge set, but not on the arc set of the graph Γ, and it is called 2-path-transitive if Aut Γ is transitive on the set of the 2-paths. In this paper we construct a class of 2-path-transitive graphs from some symmetric groups, based on which a new class of half-arc-transitive graphs is given. [ABSTRACT FROM AUTHOR]

In a witness rectangle graph (WRG) on vertex point set P with respect to witness point set W in the plane, two points x, y in P are adjacent whenever the open isothetic rectangle with x and y as opposite corners contains at least one point in W. WRGs are representative of a larger family of witness proximity graphs introduced in two previous papers. We study graph-theoretic properties of WRGs. We prove that any WRG has at most two non-trivial connected components. We bound the diameter of the non-trivial connected components of a WRG in both the one-component and two-component cases. In the latter case, we prove that a graph is representable as a WRG if and only if each component is a connected co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. In addition, we prove that a WRG with no isolated vertices has domination number at most four. Moreover, we show that any combinatorial graph can be drawn as a WRG using a combination of positive and negative witnesses. Finally, we conclude with some related results on the number of points required to stab all the rectangles defined by a set of n points. [ABSTRACT FROM AUTHOR]

Let G be a graph. The core of G, denoted by G, is the subgraph of G induced by the vertices of degree Δ( G), where Δ( G) denotes the maximum degree of G. A k -edge coloring of G is a function f : E( G) → L such that | L| = k and f ( e) ≠ f ( e) for all two adjacent edges e and e of G. The chromatic index of G, denoted by χ′( G), is the minimum number k for which G has a k-edge coloring. A graph G is said to be Class 1 if χ′( G) = Δ( G) and Class 2 if χ′( G) = Δ( G) + 1. In this paper it is shown that every connected graph G of even order whose core is a cycle of order at most 13 is Class 1. [ABSTRACT FROM AUTHOR]

A (finite) sequence of nonnegative integers is graphic if it is the degree sequence of some simple graph G. Given graphs G and G, we consider the smallest integer k such that for every k-term graphic sequence π, there is some graph G with degree sequence π with $${G_1 \subseteq G}$$ or with $${G_2 \subseteq \overline{G}}$$ . When the phrase 'some graph' in the prior sentence is replaced with 'all graphs', the smallest such integer k is the classical Ramsey number r( G, G). Thus we call this parameter for degree sequences the potential-Ramsey number and denote it r( G, G). In this paper, we give exact values for r( K, K), r( C, K), and r( P, K) and consider situations where r( G, G) = r( G, G). [ABSTRACT FROM AUTHOR]

In this paper info cyclic connectivity is studied in relation to certain matching properties in regular graphs. Results giving sufficient conditions in terms of cyclic connectivity for regular graphs to be factor-critical, to be 3-factor-critical, to have the restricted matching properties E( m, n) and to have defect- d matchings are obtained. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new closure concept for spanning k-trees. A k-tree is a tree with maximum degree at most k. We prove that: Let G be a connected graph and let u and v be nonadjacent vertices of G. Suppose that $${\sum_{w \in S}d_G(w) \geq |V(G)| -1}$$ for every independent set S in G of order k with $${u,v \in S}$$. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. This result implies Win's result (Abh Math Sem Univ Hamburg, 43:263-267, ) and Kano and Kishimoto's result (Graph Comb, ) as corollaries. [ABSTRACT FROM AUTHOR]

Union-free families of subsets of [ n] = {1, . . . , n} have been studied in Frankl and Füredi (Eur J Combin 5:127-131, ). In this paper, we provide a complete characterization of maximal symmetric difference-free families of subsets of [ n]. [ABSTRACT FROM AUTHOR]

Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, ). For a graph G and an integer s > 0 and for $${u, v \in V(G)}$$ with u ≠ v, an ( s; u, v)-path-system of G is a subgraph H consisting of s internally disjoint ( u, v)-paths. A graph G is spanning s-connected if for any $${u, v \in V(G)}$$ with u ≠ v, G has a spanning ( s; u, v)-path-system. The spanning connectivity κ*( G) of a graph G is the largest integer s such that G has a spanning ( k; u, v)-path-system, for any integer k with 1 ≤ k ≤ s, and for any $${u, v \in V(G)}$$ with u ≠ v. An edge counter-part of κ*( G), defined as the supereulerian width of a graph G, has been investigated in Chen et al. (Supereulerian graphs with width s and s-collapsible graphs, ). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207-222, ) proved that if a graph G has 2 edge-disjoint spanning trees, and if L( G) is the line graph of G, then κ*( L( G)) ≥ 2 if and only if κ( L( G)) ≥ 3. In this paper, we extend this result and prove that for any integer k ≥ 2, if G, the core of G, has k edge-disjoint spanning trees, then κ*( L( G)) ≥ k if and only if κ( L( G)) ≥ max{3, k}. [ABSTRACT FROM AUTHOR]

Let G be an edge-colored graph. A heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d( v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. In this paper, we prove that if G is an edge-colored triangle-free graph of order n ≥ 9 and $${d^c(v) \geq \frac{(3-\sqrt{5})n}{2}+1}$$ for each vertex v of G, G has a heterochromatic C. [ABSTRACT FROM AUTHOR]

A set S of vertices of a graph is a defensive k-alliance if every vertex $${v\in S}$$ has at least k more neighbors in S than it has outside of S. Analogously, a set S is an offensive k-alliance if every vertex in the neighborhood of S has at least k more neighbors in S than it has outside of S. Also, a powerful k-alliance is a set S of vertices of the graph, which is both defensive k-alliance and offensive ( k + 2)-alliance. A powerful k-alliance is called global if it is a dominating set. In this paper we show that for k ≥ 0, no graph is partitionable into global powerful k-alliances and, for k ≤ −1, we obtain upper bounds on the maximum number of sets belonging to a partition of a graph into global powerful k-alliances. In addition, we study the close relationships that exist between partitions of a Cartesian product graph, Γ × Γ, into (global) powerful ( k + k)-alliances and partitions of Γ into (global) powerful k-alliances, $${i\in \{1,2\}}$$. [ABSTRACT FROM AUTHOR]

The Ahlswede-Zhang identity is an elegant sharpening of the famous LYM-inequality. Recently, we have found a parametrised identity which implies the AZ identity and characterizes deficiencies of other inequalities in combinatorics. In this paper, we show identities of half-way extraction from AZ-style identities. These identities aim to characterize more clearly terms participating in AZ identities or LYM-style inequalities. [ABSTRACT FROM AUTHOR]

A proper vertex colouring of a graph G is 2- frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2- frugally (resp. linearly) L- colourable if for a given list assignment $${L:V(G)\mapsto 2^{\mathbb N}}$$ , there exists a 2-frugal (resp. linear) colouring c of G such that $${c(v) \in L(v)}$$ for all $${v\in V(G)}$$ . If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that | L( v)| ≥ k for all $${v\in V(G)}$$, then G is 2- frugally (resp. linearly) k- choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree. [ABSTRACT FROM AUTHOR]

Let k, h be positive integers with k ≤ h. A graph G is called a [ k, h]-graph if k ≤ d( v) ≤ h for any $${v \in V(G)}$$. Let G be a [ k, h]-graph of order 2 n such that k ≥ n. Hilton (J. Graph Theory 9:193-196, ) proved that G contains at least $${\lfloor k/3\rfloor}$$ disjoint perfect matchings if h = k. Hilton's result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74-89, ), they proved that G contains at least $${\lfloor k/2\rfloor}$$ disjoint perfect matchings if k = h. In this paper, we improve Hilton's result from another direction, we prove that Hilton's result is true for [ k, k + 1]-graphs. Specifically, we prove that G contains at least $${\lfloor\frac{n}3\rfloor+1+(k-n)}$$ disjoint perfect matchings if h = k + 1. [ABSTRACT FROM AUTHOR]

Roman dominating function on a graph G is a function f : V( G) → {0, 1, 2} satisfying the condition that every vertex u for which f ( u) = 0 is adjacent to at least one vertex v for which f ( v) = 2. The weight of a Roman dominating function is the value $${f (V(G)) = \sum_{u\in V(G)} f (u)}$$. The Roman domination number, γ( G), of G is the minimum weight of a Roman dominating function on G. The Roman bondage number b( G) of a graph G with maximum degree at least two is the minimum cardinality of all sets $${E^{\prime} \subseteq E(G)}$$ for which γ( G − E′) > γ( G). In this paper we present different bounds on the Roman bondage number of planar graphs. [ABSTRACT FROM AUTHOR]

Bent and almost-bent functions on $${\mathbb{Z}_p^2}$$ are studied in this paper. By calculating certain exponential sum and using a technique due to Hou (Finite Fields Appl 10:566-582, 2004), we obtain a degree bound for quasi-bent functions, and prove that almost-bent functions on $${\mathbb{Z}_p^2}$$ are equivalent to a degenerate quadratic form. From the viewpoint of relative difference sets, we also characterize bent functions on $${\mathbb{Z}_p^2}$$ in two classes of $${\mathcal{M}}$$ 's and $${\mathcal{PS}}$$ 's, and show that the graph set corresponding to a bent function on $${\mathbb{Z}_p^2}$$ can be written as the sum of a graph set of $${\mathcal{M}}$$ 's type bent function and another group ring element. By using our characterization and some technique of permutation polynomial, we obtain the result: a bent function must be of $${\mathcal{M}}$$ 's type if its corresponding set contains more than ( p − 3)/2 flats. A problem proposed by Ma and Pott (J Algebra 175:505-525, 1995) is therefore partially answered. [ABSTRACT FROM AUTHOR]

Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. In this paper we give the means to construct infinitely many pairs of chromatically equivalent graphs where one graph in the pair is clique-separable, that is, can be obtained by identifying an r-clique in some graph H with an r-clique in some graph H, and the other graph is non-clique-separable. There are known methods for finding pairs of chromatically equivalent graphs where both graphs are clique-separable or both graphs are non-clique-separable. Although examples of pairs of chromatically equivalent graphs where only one of the graphs is clique-separable are known, a method for the construction of infinitely many such pairs was not known. Our method constructs such pairs of graphs with odd order n ≥ 9. [ABSTRACT FROM AUTHOR]

Weakly quasi-threshold graphs form a proper subclass of the well-known class of cographs by restricting the join operation. In this paper we characterize weakly quasi-threshold graphs by a finite set of forbidden subgraphs: the class of weakly quasi-threshold graphs coincides with the class of { P, co-(2 P)}-free graphs. Moreover we give the first linear-time algorithm to decide whether a given graph belongs to the class of weakly quasi-threshold graphs, improving the previously known running time. Based on the simplicity of our recognition algorithm, we can provide certificates of membership (a structure that characterizes weakly quasi-threshold graphs) or non-membership (forbidden induced subgraphs) in additional $${{\mathcal O}(n)}$$ time. Furthermore we give a linear-time algorithm for finding the largest induced weakly quasi-threshold subgraph in a cograph. [ABSTRACT FROM AUTHOR]

We discuss the range of values for the integrity of a graphs G( n, k) where G( n, k) denotes a simple graph with n vertices and k edges. Let I( n, k) and I( n, k) be the maximal and minimal value for the integrity of all possible G( n, k) graphs and let the difference be D( n, k) = I( n, k) − I( n, k). In this paper we give some exact values and several lower bounds of D( n, k) for various values of n and k. For some special values of n and for s < n we construct examples of graphs G = G( n, n + s) with a maximal integrity of I( G) = I( C) + s where C is the cycle with n vertices. We show that for k = n/6 the value of D( n, n/6) is at least $${\frac{\sqrt{6}-1}{3}n}$$ for large n. [ABSTRACT FROM AUTHOR]