Search

Let T be a tree with vertex set V (T) = { 1 , 2 , ... , n }. The Steiner distance of a subset S ⊆ V (T) of vertices of T is defined to be the number of edges in a smallest connected subtree of T that contains all the vertices of S. The k -Steiner distance matrix D k (T) of T is the ( n k ) × ( n k ) matrix whose rows and columns are indexed by subsets of vertices of size k. The entry in the row indexed by P and column indexed by Q is equal to Steiner distance of P ∪ Q. We consider the case when k = 2 and show that rank (D 2 (T)) = 2 n − p − 1 where p is the number of pendant vertices (or leaves) in T. We construct a basis B for the row space of D 2 (T) and obtain a formula for the inverse of the nonsingular square submatrix D = D 2 (T) [ B , B ]. We also compute the determinant of D and show that its absolute value is independent of the structure of T and apply it to obtain the inertia of D 2 (T). Lastly, we determine the spectrum of 2-Steiner distance matrix of the star tree. [ABSTRACT FROM AUTHOR]

One way to study the combinatorics of finite metric spaces is to study the betweenness relation associated with the metric space. In the hypergraph metrization problem, one has to find and characterize metric betweennesses with collinear triples (or alternatively, non-degenerate triangles) that coincide with the edges of a given 3-uniform hypergraph. Metrizability of different kinds of hypergraphs was investigated in the last decades. Chen showed that Steiner triple systems are not metric, while Richmond and Richmond characterized linear betweennesses, i.e. metric betweennesses that realize the complete 3-uniform hypergraph. The latter result was also generalized to pseudometric (almost-metric) betweennesses by Beaudou et al. In this paper, we further extend this theory by characterizing the largest non-linear almost-metric betweennesses that satisfy certain hereditary properties, as well as the ones that contain a small linear number of non-degenerate triangles. [ABSTRACT FROM AUTHOR]

A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph K n. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs. For each planar Hamiltonian graph G , we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of K n. [ABSTRACT FROM AUTHOR]

Let T be a tessellation composed of equilateral triangular regions, where each region has an associated positive weight. We present two methods that discretize the space based on the placement of Steiner points in the cells of T. Using such a discretization, we can use Dijkstra's algorithm for computing the shortest path in the geometric graph obtained. This will lead us to two approximation algorithms for solving the Weighted Region Problem. For a given parameter ε ∈ (0 , 1 ] , the first discretization scheme provides an approximate path that is (1 + 0.428 ε) times better than the approximation given by Aleksandrov et al. (2005) [5]. The other discretization scheme uses at least ( ε + 2 ε + 4 ε + 4) log 2 ⁡ e fewer points per segment of the triangulation with the same approximation factor. [ABSTRACT FROM AUTHOR]

Knowledge graphs (KGs) Embedding has been broadly studied in recent years. However, less light is shed on the ubiquitous hyper-relational KGs. Most existing hyper-relational KG embedding methods decompose n-ary facts into smaller tuples, undermining the structure of n-ary facts. Moreover, these models always suffer from low expressiveness and high complexity. In this work, to tackle the indecomposability issue, we represent n-ary fact as a hyperedge, keeping the integrity of fact and maintaining the vital role that primary triple plays. To address the expressiveness and complexity issue, we propose HYPER2 where we generalize hyperbolic Poincaré embedding from binary to arbitrary arity data, and we design an information aggregation module to capture the interaction between entities within and beyond triple. Extensive experiments demonstrate HYPER2 is superior to its translational and deep analogues, improving MRR and other metrics by a large margin with relatively few dimensions. Moreover, we study the side effect of literals, and we theoretically and experimentally compare the computational complexity of HYPER2 against several best-performing baselines. HYPER2 is much quicker than its counterparts. [ABSTRACT FROM AUTHOR]

A set grading on the split simple Lie algebra of type D 13 , that cannot be realized as a group-grading, is constructed by splitting the set of positive roots into a disjoint union of pairs of orthogonal roots, following a pattern provided by the lines of the projective plane over G F (3). This answers in the negative [3, Question 1.11]. Similar non-group gradings are obtained for types D n with n ≡ 1 (mod 12) , by substituting the lines in the projective plane by blocks of suitable Steiner systems. [ABSTRACT FROM AUTHOR]

In this article, we answer three questions from the paper (Das, 2021). We observe a tight lower bound for the triameter of trees in terms of order and number of leaves. We show that in a connected block graph any triametral triple of vertices contains a diametral pair and that any diametral pair of vertices can be extended to a triametral triple. We also present several open problems concerning the interplay between triametral triples, diametral pairs and peripheral vertices in median and distance-hereditary graphs. [ABSTRACT FROM AUTHOR]

The DB-GST problem is given an undirected graph G (V , E) , and a collection of groups S = { S i } i = 1 q , S i ⊆ V , find a tree that contains at least one vertex from every group S i , so that the maximum degree is minimal. This problem was motivated by On-Line algorithms Hajiaghayi (2016), and has applications in VLSI design and fast Broadcasting. In the WDB-GST problem, every vertex v has individual degree bound d v , and every e ∈ E has a cost c (e) > 0. The goal is, to find a tree that contains at least one terminal from every group, so that for every v , d e g T (v) ≤ d v , and among such trees, find the one with minimum cost. We give the first approximation for this problem, an (O (log 2 n) , O (log 2 n)) bicriteria approximation ratio the WDB-GST problem on trees inputs. This implies an O (log 2 n) approximation for DB-GST on tree inputs. The previously best known ratio for the WDB-GST problem on trees was a bicriterion (O (log 2 n) , O (log 3 n)) (the approximation for the degrees is O (log 3 n)) ratio which is folklore. Getting O (log 2 n) approximation requires careful case analysis and was not known. Our result for WDB-GST generalizes the classic result of Garg et al. (2016) that approximated the cost within O (log 2 n) , but did not approximate the degree. Our main result is an O (log 3 n) approximation for BD-GST on Bounded Treewidth graphs. The DB-Steiner k -tree problem is given an undirected graph G (V , E) , a collection of terminals S ⊆ V , and a number k , find a tree T (V ′ , E ′) that contains at least k terminals, of minimum maximum degree. We prove that if the DB-GST problem admits a ρ ratio approximation, then the DB-Steiner k -tree problem, admits an O (log 2 k ⋅ ρ) expected approximation. We also show that if there are k groups, there exists an algorithm that is able to cover k / 4 of the groups with minimum maximal degree, then there is a deterministic O (log n ⋅ ρ) approximation for DB-Steiner k -tree problem. Using the work of Guo et al. (2020) we derive an O (log 3 n) approximation for DB-Steiner k -tree problem on general graphs, that runs in quasi-polynomial time. [ABSTRACT FROM AUTHOR]

• GIS techniques can design Steiner and road network minimum spanning trees. • Road pipelines connecting 10 plants to 1 user cost 26% more than Steiner pipelines. • Network length has higher correlation with pipe material costs than flow-rate. • Steiner layouts outperform road layouts unless material costs are not a factor. Dependence on fossil fuels has heightened global energy security issues. Anaerobic digestion (AD) is a technology that can produce biogas to reduce fossil fuel consumption. Transportation of biogas to end users may be achieved using low pressure biogas pipelines. A methodology containing two heuristics (connection based on proximity or output flowrate) is developed to optimise biogas pipeline layouts. A case study of pipeline networks serving up to 10 AD plants and 1 biogas end user is presented. A road network minimum spanning tree (MST) connecting 10 AD plants to the biogas end user is calculated to cost 26% more than a Steiner MST. Multi-criteria decision analysis (MCDA) is used to rank biogas pipeline layouts considering pipeline material cost and biogas flow-rate to the end user. In this analysis, Steiner MSTs always outperform road network MSTs, except when pipeline material cost is disregarded. Scenarios that connected via the proximity heuristic almost always outperformed those which connected via the output heuristic. [ABSTRACT FROM AUTHOR]

We consider edge decompositions of K v (3) − I , the complete 3-uniform hypergraph of order v minus a set of v / 3 mutually disjoint edges (1-factor). We prove that a decomposition into tight 6-cycles exists if and only if v ≡ 0 , 3 , 6 (mod 12) and v ≥ 6 ; and a decomposition into tight 9-cycles exists for all v ≥ 9 divisible by 3. These results are complementary to the theorems of Akin et al. [Discrete Math. 345 (2022)] and Bunge et al. [Australas. J. Combin. 80 (2021)] who settled the case of K v (3). [ABSTRACT FROM AUTHOR]

Let M be strongly minimal and constructed by a 'Hrushovski construction' with a single ternary relation. If the Hrushovski algebraization function μ is in a certain class T (μ triples) we show that for independent I with | I | > 1 , dcl ⁎ (I) = ∅ (* means not in dcl of a proper subset). This implies the only definable truly n -ary functions f (f 'depends' on each argument), occur when n = 1. We prove for Hrushovski's original construction and for the strongly minimal k -Steiner systems of Baldwin and Paolini that the symmetric definable closure, sdcl ⁎ (I) = ∅ (Definition 2.7). Thus, no such theory admits elimination of imaginaries. As, we show that in an arbitrary strongly minimal theory, elimination of imaginaries implies sdcl ⁎ (I) ≠ ∅. In particular, such strongly minimal Steiner systems with line-length at least 4 do not interpret a quasigroup, even though they admit a coordinatization if k = p n. The case structure depends on properties of the Hrushovski μ -function. The proofs depend on our introduction, for appropriate G ⊆ aut (M) (setwise or pointwise stabilizers of finite independent sets), the notion of a G -normal substructure A of M and of a G -decomposition of any finite such A. These results lead to a finer classification of strongly minimal structures with flat geometry, according to what sorts of definable functions they admit. [ABSTRACT FROM AUTHOR]

In the Directed Disjoint Paths problem, we are given a digraph D and a set of requests { (s 1 , t 1) , ... , (s k , t k) } , and the task is to find a collection of pairwise vertex-disjoint paths { P 1 , ... , P k } such that each P i is a path from s i to t i in D. This problem is NP -complete for fixed k = 2 and W [1]-hard with parameter k in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Positive results are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified part of size prescribed by a parameter. Namely, in the Disjoint Enough Directed Paths problem, given an n -vertex digraph D , a set of k requests, and non-negative integers d and s , the task is to find a collection of paths connecting the requests such that at least d vertices of D occur in at most s paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of D. Among other results, we show that the problem is W [1]-hard in DAGs with parameter d and, on the positive side, we give an algorithm in time O (n d + 2 ⋅ k d ⋅ s) and a kernel of size d ⋅ 2 k − s ⋅ ( k s ) + 2 k in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number k of terminals and p , where p = n − q and q is the size of the solution. [ABSTRACT FROM AUTHOR]

The Steiner k -eccentricity of a vertex v of a graph G is the maximum Steiner distance over all k -subsets of V (G) which contain v. In this paper Steiner 3-eccentricity is studied on trees. Some general properties of the Steiner 3-eccentricity of trees are given. A tree transformation which does not increase the average Steiner 3-eccentricity is given. As its application, several lower and upper bounds for the average Steiner 3-eccentricity of trees are derived. [ABSTRACT FROM AUTHOR]

We give lower bounds on the size and total size of clique partitions of a graph in terms of its spectral radius and minimum degree, and derive a spectral upper bound for the maximum number of edge-disjoint t -cliques. The extremal graphs attaining the bounds are exactly the block graphs of Steiner 2-designs and the regular graphs with K t -decompositions, respectively. [ABSTRACT FROM AUTHOR]

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (H 1 , H 2) -free graphs and a dichotomy for the latter problem restricted to H -free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H -free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree (assuming P ≠ NP). We also find that Edge Steiner Tree is polynomial-time solvable for (H 1 , H 2) -free graphs if and only if the treewidth of the class of (H 1 , H 2) -free graphs is bounded (subject to P ≠ NP). To obtain the latter result, we determine all pairs (H 1 , H 2) for which the class of (H 1 , H 2) -free graphs has bounded treewidth. [ABSTRACT FROM AUTHOR]

In this article, a novel metamaterial is presented that is constructed with split ring resonators (SRR) arranged in a nested square configuration. The proposed metamaterial unit cell is constructed over a 1.5 mm thick FR-4 substrate with electrical dimensions of 0.11 λ × 0.11 λ, where λ is the wavelength calculated at 2.8 GHz. The resonating patch contains five interconnected nested squares, including two square split ring resonators (SSRRs). The unit cell exhibits three distinct frequencies at 2.8 GHz, 5.8 GHz, and 11.2 GHz, with corresponding magnitudes of −45 dB, −50 dB, and −30 dB, respectively. Negative permittivity (ε-Negative) is observed in frequency ranges of 2.3–3.20 GHz, 4.4–6.9 GHz, and 10.8–11.30 GHz, with near-zero refractive index. The simulated outcome acquired in CST microwave studio is subsequently confirmed using analogous circuit modeling in Advanced System software (ADS). Moreover, the prototype of the proposed metamaterial is developed that shows similar resonances obtained in the simulation. The effective medium ratio (EMR) of the unit cell is calculated and a high EMR of 8.3 expresses the compactness of the metamaterial. Due to its structural compactness, this new metamaterial with ε-negative, near zero refractive index, and triple band resonance properties holds significant potential for wireless applications such as radar systems, satellite communications, and wireless sensor networks. • Novel structure featuring nested squares and SSRRs for triple-band ε-negative properties. • Achieves an EMR of 8.3 with five linked squares and two SSRRs in the design. • Operates at 2.8 GHz, 5.8 GHz, and 11.2 GHz, catering to S-, C-, and X-bands. • Utilizes a 1.5 mm FR-4 substrate, ensuring affordability and accessibility. • Experimental, CST, and ADS analysis confirm predicted outcomes and potential applications. [ABSTRACT FROM AUTHOR]

Techniques of producing new combinatorial structures from old ones are commonly called trades. The switching principle applies for a broad class of designs: it is a local transformation that modifies two columns of the incidence matrix. In this paper, we present a construction, which is a generalization of the switching transform for the class of Steiner 2-designs. We call this construction paramodification of Steiner 2-designs, since it modifies the parallelism of a subsystem. We study in more detail the paramodifications of affine planes, Steiner triple systems, and abstract unitals. Computational results show that paramodification can construct many new unitals. [ABSTRACT FROM AUTHOR]

The geometric 2-connected Steiner network problem asks for a shortest bridgeless network spanning a given set of terminals in the plane such that the total length of all edges of the network, as measured in the ℓ p metric, is a minimum. Using reduction from the problem of deciding the Hamiltonicity of planar cubic bipartite graphs we show that this problem is NP-hard (and NP-complete when discretised) for any constant p ≥ 2 or p = 1. Our reduction shows that the geometric 2-connected spanning network problem, i.e., the analogous problem without Steiner points, is also NP-hard for p ≥ 2 or p = 1. [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]

Two vertex-labelled polygons are compatible if they have the same clockwise cyclic ordering of vertices. The definition extends to polygonal regions (polygons with holes) and to triangulations—for every face, the clockwise cyclic order of vertices on the boundary must be the same. It is known that every pair of compatible n -vertex polygonal regions can be extended to compatible triangulations by adding O (n 2) Steiner points. Furthermore, Ω (n 2) Steiner points are sometimes necessary, even for a pair of polygons. Compatible triangulations provide piecewise linear homeomorphisms and are also a crucial first step in morphing planar graph drawings, aka "2D shape animation." An intriguing open question, first posed by Aronov, Seidel, and Souvaine in 1993, is to decide if two compatible polygons have compatible triangulations with at most k Steiner points. In this paper we prove the problem to be NP-hard for polygons with holes. The question remains open for simple polygons. [ABSTRACT FROM AUTHOR]

Let T be the group of all complex numbers z with | z | = 1. A complex unit gain graph, or simply a T -gain graph, is a triple Φ = (G , T , φ) consisting of a graph G = (V , E) , the circle group T and a gain function φ : E → → T such that φ (v i v j) = φ (v j v i) − 1 = φ (v j v i) ‾ for any adjacent vertices v i and v j. The adjacency matrix A (Φ) of the T -gain graph Φ = (G , T , φ) of order n is an n × n complex matrix (a i j) , where a i j = a j i ‾ = φ (v i v j) if v i is adjacent to v j and a i j = 0 if otherwise. The rank of a T -gain graph Φ, denoted by r (Φ) , is the rank of the adjacency matrix of Φ. Yu et al. [24] obtained some properties of inertia indexes of a T -gain graph and they characterized the T -gain unicyclic graphs with small positive or negative index. Lu [8] characterized the T -gain bicyclic graphs with rank 2 , 3 or 4. Motivated by above, we determine the rank of a T -gain unicyclic graph and classify the T -gain graphs with rank 2. [ABSTRACT FROM AUTHOR]

In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS'05), in which we are given a demand r t ∈ { 0 , 1 } for instant of time t = 0 , ... , T − 1 , along with K permit types with lengths of time δ 1 , ... , δ K and sub-additive costs. A permit is a pair (k , t ˆ) ∈ K × Z + , and it covers interval t ˆ , t ˆ + δ k). We wish to find a minimum-cost set of permits that covers every t with r t = 1. Meyerson gave deterministic O (K) -competitive and randomized O (lg K) -competitive online algorithms for this problem, as well as matching lower bounds. The first variant we propose is the multi parking permit problem, in which an arbitrary demand is given at each instant ( r t ∈ Z + ) and we may buy multiple permits to serve it. We prove that the offline version of this problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields a deterministic O (K) -competitive online algorithm and a randomized O (lg K) -competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O (lg n) -approximation algorithm and a O (lg K lg | V |) -competitive online algorithm, where n is the number of requests and | V | is the size of the input metric. The second variant we propose is the group parking permit problem, in which we also have an arbitrary demand for each instant, and each permit of type k can be either a single permit, costing γ k and covering one demand per instant of time, or a group permit, which costs M ⋅ γ k for some constant M ≥ 1 and covers an arbitrary number of demands in the interval covered by this permit. (I.e., group permits have infinite capacity.) For this version of the problem, we give an 8-approximation algorithm and a deterministic O (K) -competitive online algorithm. The first result yields an improvement on the previous best approximation algorithm for the leasing version of the rent-or-buy problem. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid (2015), in which a permit type is defined by a length of time and an integer capacity. They presented a constant approximation algorithm and a deterministic O (K) -competitive online algorithm for a hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time algorithms. Moreover, these results yield approximation and competitive online algorithms for a hierarchical leasing version of the buy-at-bulk network design problem. We also show that their original pseudo-polynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NP-hard. [ABSTRACT FROM AUTHOR]

By extending the notion of Arens regularity of bilinear mappings, we say that a bounded trilinear map on the Cartesian product of Banach spaces is Aron–Berner regular when all its six Aron–Berner extensions to the Cartesian product of the bidual spaces coincide. We give some results on the Aron–Berner regularity of certain trilinear maps. We then focus on the bidual, E ⁎ ⁎ , of a Jordan Banach triple system (E , π) , and investigate those conditions under which E ⁎ ⁎ is itself a Jordan Banach triple system under each of the Aron–Berner extensions of the triple product π. We also compare these six triple products with those arising from certain ultrafilters based on the ultrapower formulation of the principle of local reflexivity. In particular, we examine the Aron–Berner triple products on the bidual of a JB⁎-triple in relation with the so-called Dineen's theorem. Some illuminating examples are included and some questions are also left undecided. [ABSTRACT FROM AUTHOR]

Let m 1 , m 2 , n be three positive integers, m 1 < m 2 ≤ n. A (m 1 , m 2) -near-Skolem sequence of order n with defects m 1 and m 2 is a sequence S = (s 1 , s 2 , ⋯ , s 2 n − 4) of 2 n − 4 positive integers which satisfies the following two conditions: (1) For every k ∈ { 1 , 2 , ⋯ , n } ∖ { m 1 , m 2 } there are exactly two elements s i , s j ∈ S , such that s i = s j = k ; (2) If s i = s j = k then | j − i | = k. In this paper, we mainly show the existence of (m 1 , m 2) -near-Skolem sequences with m 2 − m 1 ≤ 2. We also prove that there is a (m 1 , m 2) -near-Skolem sequence when n ≥ 3 m 2 + 1. [ABSTRACT FROM AUTHOR]

An automorphism group of a design is called block-transitive if it acts transitively on the blocks. This paper gives a reduction for Steiner 3-designs admitting a block-transitive automorphism group. We prove that a block-transitive point-primitive automorphism group of a nontrivial Steiner 3-design is either affine or almost simple. [ABSTRACT FROM AUTHOR]

Not only due to the energy crisis European policymakers are exploring options to substitute natural gas with renewable hydrogen. A condition for the application of hydrogen is a functioning transportation infrastructure. However, the most efficient transport of large hydrogen quantities is still unclear, and deeper analyses are missing. A promising option is converting the existing gas infrastructure. This study presents a novel approach to develop hydrogen networks by applying the Steiner tree algorithm to derive candidates and evaluate their costs. This method uses the existing grid (brownfield) and is compared to a newly built grid (Greenfield). The goal is the technical and economic evaluation and comparison of hydrogen network candidates. The methodology is applied to the German gas grid and demand and supply scenarios covering the industry, heavy-duty transport, power, and heating sector, imports, and domestic production. Five brownfield candidates are compared to a greenfield candidate. The candidates differ by network length and pipeline diameters to consider the transported volume of hydrogen. The economic evaluation concludes that most brownfield candidates' cost is significantly lower than those of the greenfield candidate. The candidates can serve as starting points for flow simulations, and policymakers can estimate the cost based on the results. • Conceptual evaluation method for the conversion of the gas transmission grid in the context of the energy transition. • Application of Steiner Tree Algorithm to derive hydrogen network candidates. • Development of five brownfield and one greenfield candidate based on a case study for Germany. • Starting points of the systematic evaluation of hydrogen with regard to costs and security of supply. [ABSTRACT FROM AUTHOR]

The dichromatic number of D , denoted by χ → (D) , is the smallest integer k such that D admits an acyclic k -coloring. We use mader χ → (F) to denote the smallest integer k such that if χ → (D) ≥ k , then D contains a subdivision of F. A digraph F is called Mader-perfect if for every subdigraph F ′ of F , mader χ → (F ′) = | V (F ′) |. We extend octi digraphs to a larger class of digraphs and prove that it is Mader-perfect, which generalizes a result of Gishboliner, Steiner and Szabó [Dichromatic number and forced subdivisions, J. Comb. Theory, Ser. B 153 (2022) 1–30]. We also show that if K is a proper subdigraph of C ↔ 4 except for the digraph obtained from C ↔ 4 by deleting an arbitrary arc, then K is Mader-perfect. [ABSTRACT FROM AUTHOR]

A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. We use E 3 (2 d − 1 , n − 2 d + 1) to denote the 3-uniform hypergraph whose vertex set can be partitioned into two vertex classes V 1 and V 2 of size 2 d − 1 and n − 2 d + 1 , respectively, and whose edge set consists of all the triples containing at least two vertices of V 1. Let H be a 3-uniform hypergraph of order n ≥ 13 d with no isolated vertex and deg (u) + deg (v) > 2 ( n − 1 2 − n − d 2 ) for any two adjacent vertices u , v ∈ V (H). In this paper, we show that H contains a matching of size d if and only if H is not a subgraph of E 3 (2 d − 1 , n − 2 d + 1). This result improves our previous one in Zhang and Lu (2018). [ABSTRACT FROM AUTHOR]

Abstract A geometric graph is called self-approaching, if for each (ordered) pair of vertices of the graph, there exists a self-approaching (directed) path between them. A path from a vertex u to a vertex v of the graph is called self-approaching, if for any point (not just vertex) x on the path, the distance between x and any point that starts at u and moves toward x is decreasing. A path is called an increasing-chord, if it is self-approaching from both sides, source to destination and destination to source. A geometric graph is called a self-approaching t -spanner, for t > 1 , if for each pair (u , v) of vertices of the graph, there exists a self-approaching path from u to v of length at most t times the Euclidean distance between u and v. In 2015, Dehkordi et al. (2015) [16] left the problem of the existence of an increasing-chord planar geometric graph for a set of points that lie along the sides of an acute triangle, as an open problem, but they did not mention anything about the case of an obtuse triangle. In this paper, we show that for each set of points on the boundary of an obtuse triangle, there exists an increasing-chord planar geometric graph. Moreover, we show that for each set of points on the boundary of an acute triangle, there exists an increasing-chord planar geometric graph using at most three Steiner points. We also introduce weakly self-approaching geometric graphs (spanners) as a variation of self-approaching geometric graphs (spanners). A weakly self-approaching path is defined similarly to a self-approaching path, except that when a point p on the path moves from the source to the destination, the Euclidean distance between p and the destination vertex (but not all the points on the path) decreases. A weakly self-approaching geometric graph (spanner) is defined by replacing "self-approaching" by "weakly self-approaching" in the above definition. In this paper, we show that for every point set S ⊆ R d , there is a weakly self-approaching planar geometric graph spanning S. Furthermore, this study shows how to test in polynomial time, whether a given geometric graph is weakly self-approaching. Notably, the corresponding decision problem in the context of self-approaching geometric graphs in R d with d ≥ 3 is NP-hard. We also propose some algorithms for constructing a weakly self-approaching geometric t -spanner for a given point set and a real constant t > 1. Also, we show that for every point set S on the boundary of any triangle, there exists an increasing-chord t -spanner spanning S and a weakly self-approaching t -spanner spanning S , both with O (k n) edges, in which k depends only on t. [ABSTRACT FROM AUTHOR]

Abstract We introduce the concepts of k -lunes and k -lune inequalities, which form the basis for new geometric pruning rules for limiting the number of candidate full components that need to be considered when solving the Euclidean Steiner tree problem or the Euclidean 2-connected Steiner network problem. For the latter problem, these new pruning rules constitute the first empty region properties to have been developed for the problem. We show how to implement these rules efficiently and run computational experiments, indicating the extent to which they can improve the performance of state-of-the-art algorithms for these problems. [ABSTRACT FROM AUTHOR]

Abstract Anthropogenic disturbances fragmenting wildlife habitat greatly contribute to extinction risk for many species. In western Canada, four decades of oil and gas exploration have created a network of seismic lines, which are linear disturbances where seismic equipment operates. Seismic lines cause habitat fragmentation and increase predator access to intact forest, leading to declines of some wildlife populations, particularly the threatened woodland caribou, Rangifer tarandus caribou. Restoration of forests within seismic lines is an important activity to reduce habitat fragmentation and recovery caribou. We present an optimization model with the objective of guiding landscape restoration strategies that maximize the area of connected habitat for a caribou population in a fragmented landscape. We use our model to find optimal strategies for seismic line restoration in the Cold Lake Area of Alberta, Canada, a 6726-km2 expanse of boreal forest that represents prime caribou habitat. We formulate mixed integer programming models that depict the landscape as a network of interconnected habitat patches. We develop and compare formulations that emphasize the population's local or long-distance access to habitat. Optimal restoration involves a mix of two strategies: the first establishes short-distance connections between forest patches with large areas of intact habitat and the second establishes corridors between areas with known species locations and large amounts of suitable habitat. Our approach reveals the trade-offs between these strategies and finds the optimal restoration solutions under a limited budget. The approach is generalizable and applicable to other regions and species sensitive to changes in landscape-level habitat connectivity. [ABSTRACT FROM AUTHOR]

Abstract The Steiner distance of vertices in a set S is the minimum size of a connected subgraph that contain these vertices. The sum of the Steiner distances over all sets S of cardinality k is called the Steiner k -Wiener index and studied as the natural generalization of the famous Wiener index in chemical graph theory. In this paper we study the extremal structures, among trees with a given segment sequence, that maximize or minimize the Steiner k -Wiener index. The same extremal problems are also considered for trees with a given number of segments. [ABSTRACT FROM AUTHOR]

Abstract Let S be a set of at least two vertices in a graph G. A subtree T of G is a S-Steiner tree if S ⊆ V (T). Two S -Steiner trees T 1 and T 2 are edge-disjoint (resp. internally disjoint) if E (T 1) ∩ E (T 2) = ∅ (resp. E (T 1) ∩ E (T 2) = ∅ and V (T 1) ∩ V (T 2) = S). Let λ G (S) (resp. κ G (S)) be the maximum number of edge-disjoint (resp. internally disjoint) S -Steiner trees in G , and let λ k (G) (κ k (G)) be the minimum λ G (S) (resp. κ G (S)) for S ranges over all k -subsets of V (G). Clearly, λ 2 (G) (resp. κ 2 (G)) is the classical edge-connectivity λ (G) (resp. connectivity κ (G)). In this paper, we study the λ 3 -connectivity and κ 3 -connectivity of a recursive circulant G , determine λ 3 (G) = δ (G) − 1 for each recursive circulant G , and κ 3 (G) = δ (G) − 1 for each recursive circulant G except G ≅ G (2 m , 2). [ABSTRACT FROM AUTHOR]

In this paper, we study the Steiner hyper-Wiener index of a graph, which is obtained from the standard hyper-Wiener index by replacing the classical graph distance with the Steiner distance. It is shown how this index is related to the Steiner Hosoya polynomial, which generalizes similar result for the standard hyper-Wiener index. Next, we show how the Steiner 3-hyper-Wiener index of a modular graph can be expressed by using the classical graph distances. As the main result, a method for computing this index for median graphs is developed. Our method makes computation of the Steiner 3-hyper-Wiener index much more efficient. Finally, the method is used to obtain the closed formulas for the Steiner 3-Wiener index and the Steiner 3-hyper-Wiener index of grid graphs. [ABSTRACT FROM AUTHOR]

In this paper we prove that rank metric codes with special properties imply the existence of q -analogs of suitable designs. More precisely, we show that the minimum weight vectors of a [ 2 d , d , d ] dually almost MRD code C ≤ F q m 2 d ( 2 d ≤ m ) which has no code words of rank weight d + 1 form a q -Steiner system S ( d − 1 , d , 2 d ) q . This is the q-analog of a result in classical coding theory and it may be seen as a first step to prove a q-analog of the famous Assmus–Mattson Theorem. [ABSTRACT FROM AUTHOR]

A classical construction of Bose produces a Steiner triple system of order 3 n from a symmetric, idempotent latin square of order n , which exists whenever n is odd. In an application to access-balancing in storage systems, certain Bose triple systems play a central role. A natural question arises: For which orders v does there exist a resolvable Bose triple system? Elementary counting establishes the necessary condition that v ≡ 9 (mod 18). For specific Bose triple systems that optimize an access metric, we show that v ≡ 9 (mod 18) is also sufficient. [ABSTRACT FROM AUTHOR]

Strong Steiner ω -categories are a class of ω -categories that admit algebraic models in the form of chain complexes, whose formalism allows for several explicit computations. The conditions defining strong Steiner ω -categories are traditionally expressed in terms of the associated chain complex, making them somewhat disconnected from the ω -categorical intuition. The purpose of this paper is to characterize this class as the class of ω -categories generated by polygraphs that satisfy a loop-freeness condition that does not make explicit use of the associated chain complex and instead relies on the categorical features of ω -categories. [ABSTRACT FROM AUTHOR]

In this paper we give a simple and effective tool to analyze a given Kirkman triple system of order 15 and determine which of the seven well-known non-isomorphic KTS(15)s it is isomorphic to. Our technique refines and improves the lacing of distinct parallel classes introduced by F. N. Cole, by means of the notion of residual triple defined by G. Falcone and the present author in a previous paper. Unlike Cole's original lacing scheme, our algorithm allows one to distinguish two KTS(15)s also in the harder case where the two systems have the same underlying Steiner triple system. In the special case where the common STS is #19, an alternative method is given by means of the 1-factorizations of the complete graph K 8 associated to the two KTSs. Moreover, we present three new visual solutions to the schoolgirl problem, and we catalogue most of the classical (or interesting) solutions in the literature in terms of what KTS(15)s they are isomorphic to. This paper provides background on a classical topic, while shedding new light on the problem as well. [ABSTRACT FROM AUTHOR]

Chung and Graham conjectured (in 1981) that n points in the unit square [ 0 , 1 ] 2 can be connected by a rectilinear Steiner tree of length at most n + 1 . Here we confirm this conjecture for small values of n , and for some new infinite sequences of values of n (but not for all n ). As an interesting byproduct we obtain close rational approximations of n from below, for those n . [ABSTRACT FROM AUTHOR]

The unique Steiner triple system of order 7 has a point-block incidence graph known as the Heawood graph. Motivated by questions in combinatorial matrix theory, we consider the problem of constructing a faithful orthogonal representation of this graph, i.e., an assignment of a vector in C d to each vertex such that two vertices are adjacent precisely when assigned nonorthogonal vectors. We show that d = 10 is the smallest number of dimensions in which such a representation exists, a value known as the minimum semidefinite rank of the graph, and give such a representation in 10 real dimensions. We then show how the same approach gives a lower bound on this parameter for the incidence graph of any Steiner triple system, and highlight some questions concerning the general upper bound. [ABSTRACT FROM AUTHOR]

Summary An excessive number of Steiner points may be inserted during the process of boundary recovery for constrained tetrahedral mesh generation, and these Steiner points are harmful in some circumstances. In this study, a new flip named shell transformation is proposed to reduce the usage of Steiner points in boundary recovery and thus to improve the performance of boundary recovery in terms of robustness, efficiency and element quality. Shell transformation searches for a local optimal mesh among multiple choices. Meanwhile, its recursive callings can perform flips on a much larger element set than a single flip, thereby leading the way to a better local optimum solution. By employing shell transformation properly, a mesh that intersects predefined constraints intensively can be transformed to another one with much fewer intersections, thus remarkably reducing the occasions of Steiner point insertion. Besides, shell transformation can be used to remove existing Steiner points by flipping the mesh aggressively. Meshing examples for various industrial applications and surface inputs mainly composed of stretched triangles are presented to illustrate how the improved algorithm works on difficult boundary constrained meshing tasks. [ABSTRACT FROM AUTHOR]

Hom-Lie triple systems endowed with a symmetric invariant nondegenerate bilinear form are called quadratic Hom-Lie triple systems. In this work, we introduce the notion of double extension of Hom-Lie triple systems so that we can give an inductive description of quadratic Hom-Lie triple systems. [ABSTRACT FROM AUTHOR]

Dirac showed that in a ( k − 1 ) -connected graph there is a path through each k vertices. The path k -connectivity π k ( G ) of a graph G , which is a generalization of Dirac’s notion, was introduced by Hager in 1986. It is natural to introduce the concept of path k -edge-connectivity ω k ( G ) of a graph G . Denote by G ○ H the lexicographic product of two graphs G and H . In this paper, we prove that ω 3 ( G ∘ H ) ≥ ω 3 ( G ) ⌊ 3 | V ( H ) | 4 ⌋ for any two graphs G and H . Moreover, the bound is sharp. We also derive an upper bound of ω 3 ( G ○ H ), that is, ω 3 ( G ∘ H ) ≤ min { 2 ω 3 ( G ) | V ( H ) | 2 , δ ( H ) + δ ( G ) | V ( H ) | } . We demonstrate the usefulness of the proposed constructions by applying them to some instances of lexicographic product networks. [ABSTRACT FROM AUTHOR]

In this paper, the cohomology theory is given in order to study δ -Lie color triple systems. Moreover, 1-parameter formal deformations, Nijenhuis operators and abelian extensions of δ -Lie color triple systems are discussed by suitable cohomology. [ABSTRACT FROM AUTHOR]

• Show that an interesting transformation on trees is monotone with respect to the average Steiner 3-eccentricity. • Establish some sharp bounds on the average Steiner 3-eccentricity among trees with a given degree sequence (resp. segment sequence, number of segments). • Using the majorization theory and our obtained results to characterize extremal graphs among the trees with some given classical parameters. The Steiner k -eccentricity of a vertex in a graph G is the maximum Steiner distance over all k -subsets containing the vertex. The average Steiner k -eccentricity of G is the mean value of all vertices' Steiner k -eccentricities in G. Let T n be the set of all n -vertex trees, T n , Δ be the set of n -vertex trees with maximum degree Δ , T n , Δ k be the set of n -vertex trees with exactly k vertices of a given maximum degree Δ , and let MT n k be the set of n -vertex trees with exactly k vertices of maximum degree. In this paper, we first determine the sharp upper bound on the average Steiner 3-eccentricity of n -vertex trees with a given degree sequence. The corresponding extremal graphs are characterized. Consequently, together with majorization theory, all graphs among T n , Δ k (resp. T n , Δ , MT n k , T n) having the maximum average Steiner 3-eccentricity are identified. Then we characterize the unique n -vertex tree with a given segment sequence having the minimum average Steiner 3-eccentricity. Finally, we determine all n -vertex trees with a given number of segments having the minimum average Steiner 3-eccentricity. [ABSTRACT FROM AUTHOR]

The prize-collecting Steiner tree problem in graphs (PCSPG) , as well as its rooted variant ( RPCST ), are target problems of the 11th DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science) Implementation Challenge held in collaboration with ICERM (the Institute for Computational and Experimental Research in Mathematics). To solve these two problems, this paper proposes a knowledge-guided local search algorithm (K-ILS), 1 1 This paper extends [15], which was presented at the workshop of the 11th DIMACS Implementation Challenge, but has not been formally published. which integrates dedicated search strategies and explores structure information of problem instances. K-ILS uses an effective swap-vertex operator for tree transformation associated with a discriminating auxiliary evaluation function as well as several knowledge-guided perturbation strategies. K-ILS additionally employs two new path-based move operators to generate neighboring solutions. The computational results achieved on the benchmark instances of the 11th DIMACS Implementation Challenge using the same computing platform and competition rules demonstrate that K-ILS performs very well compared to the leading algorithms of the challenge. We report additional experiments to analyze the impact of the key components to the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

A ternary [ 66 , 10 , 36 ] 3 -code admitting the Mathieu group M 12 as a group of automorphisms has recently been constructed by N. Pace, see Pace (2014). We give a construction of the Pace code in terms of M 12 as well as a combinatorial description in terms of the small Witt design, the Steiner system S ( 5 , 6 , 12 ) . We also present a proof that the Pace code does indeed have minimum distance 36 . [ABSTRACT FROM AUTHOR]

We consider the problem of classifying trades in Steiner triple systems such that each block of the trade contains one of three fixed elements. We show that the fundamental building blocks for such trades are 3 -regular graphs that are 1 -factorisable. In the process we also generate all possible 2 - and 3 -way simultaneous edge colourings of graphs with maximum degree 3 using at most 3 colours, where multiple edges but not loops are allowed. Moreover, we generate all possible Latin trades within three rows. [ABSTRACT FROM AUTHOR]