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]