Art of Discrete and Applied Mathematics

The hierarchical and the generalized hierarchical product of graphs, together with their multiary and rooted versions, are variants of the Cartesian product. They are not commutative, and only the rooted versions are associative.We prove that finite connected graphs have unique prime factorizations with respect to the rooted hierarchical product, the multiary hierarchical product, and the rooted generalized hierarchical product. For the generalized hierarchical product, we disprove a claim about unique prime factorization by Anderson, Guob, Tenney, and Wash from 2017. We also describe the interrelation between the automorphism groups of connected graphs with the groups of their prime factors in the cases of unique prime factorization, and in the case of the standard prime factorization with respect to the hierarchical product. For finite trees, we show that their prime factors can be computed in subquadratic time.

Wilfried Imrich

Rafał Kalinowski

Monika Pilśniak

The Art of Discrete and Applied Mathematics

Hierarchical products of graphs

图的分层积

An arc-colored tournament is said to be k-spanning for an integer k ≥ 1 if the union of its arc-color classes of maximal valency at most k is the arc set of a strongly connected digraph. It is proved that isomorphism testing of k-spanning tournaments is fixed-parameter tractable.

Vikraman Arvind

Ilia Ponomarenko

Grigory Ryabov

Isomorphism testing of k-spanning tournaments is fixed parameter tractable

k-支撑锦标赛同构测试是固定参数易处理的

The connected sum Z of two root graphs of order n is obtained by gluing them together along a common subgraph G of order n − 1. The two vertices of Z not in G are called terminal vertices. The edged connected sum Z + e is obtained from Z by adding the edge joining the terminal vertices. We consider the case when the root graphs have the same μ–eigenspace of the 0–1 adjacency matrix of dimension one. We show that the μ–eigenspace imposes structural constraints on Z and Z + e, depending on the type of the two vertices. For μ = 0, we investigate the electrical behaviour of a molecular electronic device with structure Z or Z + e, connected at the terminal vertices in a circuit across a small bias voltage. It transpires that the device will be a conductor or insulator depending on the type of the terminal vertices in the 0–eigenspace. We show that conductivity or its barring distinguishes between Z and Z + e.

Irene Sciriha

Connected sum of graphs as molecular electronic devices

图的连通和作为分子电子器件

We present some results on the harmonious colourings of the Levi graph of a 2-design, focusing on Steiner 2-design. It is easily seen that the harmonious chromatic number of such a Levi graph is at least the number of points of the design: we study and construct Banff designs, that is designs such that this lower bound is attained.

Marco Buratti

Francesca Merola

Anamari Nakic

Christian Rubio-Montiel

Banff designs: difference methods for coloring incidence graphs

班夫设计：用于着色关联图的差异方法

We present some methods for constructing connected spatial geometric configurations $(p_{q}, n_{k})$ of points and lines, preserved by the same rotations (and reflections) of Euclidean space $E^{3}$ as the chosen Platonic solid. In this paper we are primarily interested in balanced configurations $(n_{3}), (n_{4})$ and $(n_{5})$, but also in unbalanced configurations $(p_{3},n_{4}), (p_{3}, n_{5})$ and $(p_{4}, n_{5})$.

Jurij Kovič

Aleksander Simonič

Platonic configurations of points and lines

点和线的柏拉图构型

We present simple, geometric constructions for small regular graphs of girth 7 from the incidence graphs of some generalized quadrangles. We obtain infinite families of (q − 1)-regular, q-regular and (q + 1)-regular graphs of girth 7, for q a prime power. Some of them have the smallest order known so far.

Gyorgy Kiss

Geometric constructions of small regular graphs with girth 7

几何构造具有围长7的小正则图

Publication Information	Publisher: University of Primorska，Publishing cycle: ，Journal Type: journal，Open Access Journals: No
Basic data	Year of publication: 2018，Proportion of original research papers: 0.00%，Self Citation Rate:N.A.， Gold OA Rate: 0.00%

Art of Discrete and Applied Mathematics

Journal Citation Format

A journal article with 1 author

A journal article with 2 authors

A journal article with 3 authors

A journal article with 5 or more authors

Books Citation Format

Thesis Citation Format

Web sites Citation Format

Patent Citation Format

Staying up late manually editing references? ivySCI automatically matches journals and helps you generate references with a single click.

Share Submission Experience

Hierarchical products of graphs

Isomorphism testing of k-spanning tournaments is fixed parameter tractable

Connected sum of graphs as molecular electronic devices

Banff designs: difference methods for coloring incidence graphs

Platonic configurations of points and lines

Banff designs: difference methods for coloring incidence graphs

Platonic configurations of points and lines

Geometric constructions of small regular graphs with girth 7

Isomorphism testing of k-spanning tournaments is fixed parameter tractable

Connected sum of graphs as molecular electronic devices

ISSN	2590-9770
h-index	6