Search

Let G be a graph with vertex set V (G) and edge set E (G) , and let d (u , w) denote the length of a u − w geodesic in G. For any vertex v ∈ V (G) and any edge e = x y ∈ E (G) , let d (e , v) = min { d (x , v) , d (y , v) }. For any distinct edges e 1 , e 2 ∈ E (G) , let R { e 1 , e 2 } = { z ∈ V (G) : d (z , e 1) ≠ d (z , e 2) }. Kelenc, Tratnik and Yero [Discrete Appl. Math. 251 (2018) 204-220] introduced the notion of an edge resolving set and the edge dimension of a graph: A vertex subset S ⊆ V (G) is an edge resolving set of G if | S ∩ R { e 1 , e 2 } | ≥ 1 for any distinct edges e 1 , e 2 ∈ E (G) , and the edge dimension , edim (G) , of G is the minimum cardinality among all edge resolving sets of G. For a function g defined on V (G) and for U ⊆ V (G) , let g (U) = ∑ s ∈ U g (s). A real-valued function g : V (G) → [ 0 , 1 ] is an edge resolving function of G if g (R { e 1 , e 2 }) ≥ 1 for any distinct edges e 1 , e 2 ∈ E (G). The fractional edge dimension , edim f (G) , of G is min { g (V (G)) : g is an edge resolving function of G }. Note that edim f (G) reduces to edim (G) if the codomain of edge resolving functions is restricted to { 0 , 1 }. In this paper, we introduce and study the fractional edge dimension of graphs, and we obtain some general results on the edge dimension of graphs. We show that there exist two non-isomorphic graphs on the same vertex set with the same edge metric coordinates. We construct two graphs G and H such that H ⊂ G and both edim (H) − edim (G) and edim f (H) − edim f (G) can be arbitrarily large. We show that a graph G with edim (G) = 2 cannot have K 5 or K 3 , 3 as a subgraph, and we construct a non-planar graph H satisfying edim (H) = 2. It is easy to see that, for any connected graph G of order at least three, 1 ≤ edim f (G) ≤ | V (G) | 2 ; we characterize graphs G satisfying edim f (G) = 1 and examine some graph classes satisfying edim f (G) = | V (G) | 2 . We also determine the fractional edge dimension for some classes of graphs. [ABSTRACT FROM AUTHOR]

A (d , h) -decomposition of a graph G is an ordered pair (D , 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) with maximum out-degree at most d. In this paper, we prove that for l ∈ { 5 , 6 , 7 , 8 , 9 } , every planar graph without 4- and l -cycles is (2 , 1) -decomposable. As a consequence, for every planar graph G without 4- and l -cycles, there exists a matching M , such that G − M is 3-DP-colorable and has Alon-Tarsi number at most 3. In particular, G is 1-defective 3-DP-colorable, 1-defective 3-paintable and 1-defective 3-choosable. These strengthen the results in [Discrete Appl. Math. 157 (2) (2009) 433–436] and [Discrete Math. 343 (2020) 111797]. [ABSTRACT FROM AUTHOR]

Given a real number α ∈ (0 , 1) , we define the Webster sequence of density α to be W α = (⌈ (n − 1 / 2) / α ⌉) n ∈ N , where ⌈ x ⌉ is the ceiling function. It is known that if α and β are irrational with α + β = 1 , then W α and W β partition N. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of N into sequences W α , W β , W γ with α , β , γ irrational. In this paper, we consider the question of how close one can come to a three-part partition of N into Webster sequences with prescribed densities α , β , γ. We show that if α , β , γ are irrational with α + β + γ = 1 , there exists a partition of N into sequences of densities α , β , γ , in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the n th element of each sequence in O (1) time and the second algorithm gives the assignment of the m th positive integer to a sequence in O (1) time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider the homogeneous m -machine scheduling problem where unit-time jobs have to be scheduled within their time windows so that, for any subset of machines, the set of the time units at which at least one machine is busy, is an interval. For this problem, a time assignment of the jobs satisfying the time windows constraints is a schedule if it has a pyramidal profile and is a k -schedule if this profile property is satisfied up to level k only. We develop a generic algorithm to solve the problem and show it is correct using a proof that mainly relies on a necessary and sufficient condition for a schedule to exist proved in a previous paper. We finally show that the generic algorithm is polynomial. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling m -machine scheduling problem. [ABSTRACT FROM AUTHOR]

Let r ≥ 2 and r be even. An r -hypergraph G on n vertices is called odd-colorable if there exists a map φ : [ n ] → [ r ] such that for any edge { j 1 , j 2 , … , j r } of G , we have φ ( j 1 ) + φ ( j 2 ) + ⋅ ⋯ ⋅ + φ ( j r ) ≡ r ∕ 2 ( mod r ) . In this paper, we first determine that, if r = 2 q ( 2 t + 1 ) and n ≥ 2 q ( 2 q − 1 ) r , then the maximum chromatic number in the class of the odd-colorable r -hypergraphs on n vertices is 2 q , which answers a question raised by V. Nikiforov recently in Nikiforov (2017). We also study some applications of the spectral symmetry of the odd-colorable r -hypergraphs given in the same paper by V. Nikiforov. We show that the Laplacian spectrum S p e c ( L ( G ) ) and the signless Laplacian spectrum S p e c ( Q ( G ) ) of an r -hypergraph G are equal if and only if r is even and G is odd-colorable. As an application of this result, we give an affirmative answer for the remaining unsolved case r ⁄ ≡ 0 ( m o d 4 ) of a question raised in Shao et al. (2015) about whether S p e c ( L ( G ) ) = S p e c ( Q ( G ) ) implies that L ( G ) and Q ( G ) have the same H-spectrum. [ABSTRACT FROM AUTHOR]

Let S be a set of at least two vertices in a graph G. A subtree T of G is an S -Steiner tree if S ⊆ V (T). Two S -Steiner trees T 1 and T 2 are internally disjoint (resp. edge-disjoint) if E (T 1) ∩ E (T 2) = 0̸ and V (T 1) ∩ V (T 2) = S (resp. E (T 1) ∩ E (T 2) = 0̸). Let κ G (S) (resp. λ G (S)) be the maximum number of internally disjoint (resp. edge-disjoint) S -Steiner trees in G , and let κ k (G) (resp. λ k (G)) be the minimum κ G (S) (resp. λ G (S)) for S ranges over all k -subsets of V (G). It is well-known that the connectivity of the line graph of a graph G is closely related to the edge-connectivity of G. Chartrand et al., Li et al., and Li et al. showed that κ k (L (G)) ≥ λ k (G) for k = 2 , 3 , 4 , respectively. In [Discrete Math. 341(2018), 1945–1951.], Li et al. also proposed the following conjecture: κ k (L (G)) ≥ λ k (G) for integer k ≥ 2 and a graph G with at least k vertices. In this paper, we show that κ k (L (G)) ≥ λ k (G) − m a d (G) 2 2 for general k , where m a d (G) is the maximum average degree of a graph G. We also show that κ k (L (G)) ≥ λ k (G) − r 2 2 for any integers k and r such that k ≤ r 2 . Finally, we show that the conjecture holds for k = 5 , and the conjecture holds for the wheel graph and the complete bipartite graph K 3 , n. [ABSTRACT FROM AUTHOR]

This paper provides new results on the application of semidefinite optimization to satisfiability by studying the connection between semidefinite optimization and minimal unsatisfiability. We use a semidefinite least squares problem to assign weights to the clauses of a propositional formula in conjunctive normal form. We then show that these weights are a measure of the necessity of each clause in rendering the formula unsatisfiable, the weight of a necessary clause is strictly greater than the weight of any unnecessary clause. In particular, we show the following results: first, if a formula is minimal unsatisfiable, then all of its clauses have the same weight; second, if a clause does not belong to any minimal unsatisfiable subformula, then its weight is zero. An additional contribution of this paper is a demonstration of how the infeasibility of a semidefinite optimization problem can be tested using a semidefinite least squares problem by extending an earlier result for linear optimization. The connection between the semidefinite least squares problem and Farkas’ Lemma for semidefinite optimization is also discussed. [ABSTRACT FROM AUTHOR]

This is a survey or exposition of a particular collection of results and open problems involving snarks — simple “cubic” (3-valent) graphs for which, for nontrivial reasons, the edges cannot be 3-colored. The results and problems here are rooted in a series of papers by László Kászonyi that were published in the early 1970s. The problems posed in this survey paper can be tackled without too much specialized mathematical preparation, and in particular seem well suited for interested undergraduate mathematics students to pursue as independent research projects. This survey paper is intended to facilitate research on these problems. [ABSTRACT FROM AUTHOR]

Given a linear equation L , a set A of integers is L -free if A does not contain any ‘non-trivial’ solutions to L . This notion incorporates many central topics in combinatorial number theory such as sum-free and progression-free sets. In this paper we initiate the study of (parameterised) complexity questions involving L -free sets of integers. The main questions we consider involve deciding whether a finite set of integers A has an L -free subset of a given size, and counting all such L -free subsets. We also raise a number of open problems. [ABSTRACT FROM AUTHOR]

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]

The generalized Wiener polarity index of a graph G , denoted by W k ( G ) , is the number of unordered pairs of vertices that are at distance k in G. In this paper, we characterize the extremal trees with respect to the index among all trees of order n and diameter d , which partially answers a question of Bollobás and Tyomkyn (2012) and also generalizes some results of Deng et al. (2010). [ABSTRACT FROM AUTHOR]

For positive integers k and r , a ( k , r )-coloring of a graph G is a proper k -coloring of the vertices such that every vertex of degree d is adjacent to vertices with at least min { d , r } different colors. The r -hued chromatic number of a graph G , denoted by χ r ( G ) , is the smallest integer k such that G has a ( k , r ) -coloring. In Song et al. (2014), it is conjectured that if r ≥ 8 , then every planar graph G satisfies χ r ( G ) ≤ ⌈ 3 r 2 ⌉ + 1 . Wegner in 1977 conjectured that the above-mentioned conjecture holds when r = Δ ( G ) . This conjecture, if valid, would be best possible in some sense. In this paper, we prove that, if G is a planar graph and r ≥ 8 , then χ r ( G ) ≤ 2 r + 16 . [ABSTRACT FROM AUTHOR]

An edge-coloured path is rainbow if its edges have distinct colours. For a connected graph G , the rainbow connection number (resp. strong rainbow connection number ) of G is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by a rainbow path (resp. rainbow geodesic). These two graph parameters were introduced by Chartrand, Johns, McKeon, and Zhang in 2008. Krivelevich and Yuster generalised this concept to the vertex-coloured setting. Similarly, Liu, Mestre, and Sousa introduced the version which involves total-colourings. Dorbec, Schiermeyer, Sidorowicz, and Sopena extended the concept of the rainbow connection to digraphs. In this paper, we consider the (strong) total rainbow connection number of digraphs. Results on the (strong) total rainbow connection number of biorientations of graphs, tournaments, and cactus digraphs are presented. [ABSTRACT FROM AUTHOR]

An arc-coloured digraph D is alternating if whenever ( u , v ) and ( v , w ) are arcs in D they are of different colours. In an arc coloured digraph D , a subset K ⊂ V ( D ) of vertices of D is a kernel by alternating paths (or alternating kernel ) if it is absorbent and independent by directed alternating paths. In this paper we prove sufficient conditions for the existence of alternating kernels in arc-coloured tournaments, quasi-transitive digraphs, and k -partite digraphs. [ABSTRACT FROM AUTHOR]

In this paper we continue studying the independent transversal domination number in a graph, i.e., the cardinality of a smallest dominating set which intersects each maximum independent set. As our main result, we prove two upper bounds on the independent transversal domination number in terms of the order and minimum degree of a graph. [ABSTRACT FROM AUTHOR]

A matching in a hypergraph H is a set of pairwise disjoint hyperedges. The matching number ν ( H ) of H is the size of a maximum matching in H . A subset D of vertices of H is a dominating set of H if for every v ∈ V ∖ D there exists u ∈ D such that u and v lie in an hyperedge of H . The cardinality of a minimum dominating set of H is the domination number of H , denoted by γ ( H ) . It was proved that γ ( H ) ≤ ( r − 1 ) ν ( H ) for r -uniform hypergraphs and the 2-uniform hypergraphs (graphs) achieving equality γ ( H ) = ν ( H ) have been characterized. In this paper we generalize the inequality γ ( H ) ≤ ( r − 1 ) ν ( H ) to arbitrary hypergraph of rank r and we completely characterize the extremal hypergraphs H of rank 3 achieving equality γ ( H ) = ( r − 1 ) ν ( H ) . [ABSTRACT FROM AUTHOR]

The spectrum of a first order sentence is the set of all α such that G ( n , n − α ) does not obey zero–one law with respect to this sentence. In this paper, we prove that the minimal number of quantifier alternations of a first order sentence with infinite spectrum equals 3. We have also proved that the spectrum of a first-order sentence with quantifier depth 4 has no limit points except possibly the points 1 ∕ 2 and 3 ∕ 5 . [ABSTRACT FROM AUTHOR]

For a graph G , we denote by σ 2 ( G ) the minimum degree sum of two non-adjacent vertices if G is non-complete; otherwise, σ 2 ( G ) = + ∞ . In this paper, we prove the following two results: (i) If s 1 , s 2 ≥ 2 are integers and G is a non-complete graph with σ 2 ( G ) ≥ 2 ( s 1 + s 2 + 1 ) − 1 , then G contains two vertex-disjoint subgraphs H 1 and H 2 such that each H i is a graph of order at least s i + 1 with σ 2 ( H i ) ≥ 2 s i − 1 . (ii) If s 1 , s 2 ≥ 2 are integers and G is a triangle-free graph of order at least 3 with σ 2 ( G ) ≥ 2 ( s 1 + s 2 ) − 1 , then G contains two vertex-disjoint subgraphs H 1 and H 2 such that each H i is a graph of order at least 2 s i with σ 2 ( H i ) ≥ 2 s i − 1 . By using this result, we also give some corollaries concerning degree conditions for the existence of k vertex-disjoint cycles. [ABSTRACT FROM AUTHOR]

The allowed patterns of a map are those permutations in the same relative order as the initial segments of orbits realized by the map. In this paper, we characterize and provide enumerative bounds for the allowed patterns of signed shifts, a family of maps on infinite words. [ABSTRACT FROM AUTHOR]

An edge-coloured connected graph G is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses k colours then G is called k -rainbow connected. The rainbow connection number of G , denoted by rc ( G ) , is the minimum k such that G is k -rainbow connected. Even the problem to decide whether rc ( G ) = 2 is NP-complete. It has been shown that if G is a connected graph of order n and size m with n − 2 2 + 2 ≤ m ≤ n − 1 2 , then 2 ≤ rc ( G ) ≤ 3 . In this paper we will present sufficient conditions for graphs G of this size to fulfil rc ( G ) = 2 depending on vertex degrees. [ABSTRACT FROM AUTHOR]