Art of Discrete and Applied Mathematics

Sela Fried

Toufik Mansour

The Art of Discrete and Applied Mathematics

On the maximal sum of the entries of a matrix power

关于矩阵幂的元素和的最大值

Given vertex valencies admissible for a self-dual polyhedral graph, we describe an algorithm to explicitly construct such a polyhedron. Inputting in the algorithm permutations of the degree sequence can give rise to non-isomorphic graphs. As an application, we find as a function of n ≥ 3 the minimal number of vertices for a self-dual polyhedron with at least one vertex of degree i for each 3 ≤ i ≤ n, and construct such polyhedra. Moreover, we find a construction for non-self-dual polyhedral graphs of minimal order with at least one vertex of degree i and at least one i-gonal face for each 3 ≤ i ≤ n. Another application is to rigidity theory, since the constructed families of polyhedra are generic circuits, and globally rigid in the plane.

Riccardo W. Maffucci

Self-dual polyhedra of given degree sequence

给定度序列的自对偶多面体

A k-coupon coloring of a graph G without isolated vertices is an assignment of colors from [k] = {1, 2, …, k} to the vertices of G such that the neighborhood of every vertex of G contains vertices of all colors from [k]. The maximum k for which a k-coupon coloring exists is called the coupon coloring number of G. In this paper, we have studied the coupon coloring number of Lexicographic product of graphs G and H if G has a Hamiltonian path. We have found a sharp bound for the coupon coloring number of Lexicographic product of connected graphs.

Reji Thankachan

Pavithra Rajamani

Coupon coloring of lexicographic product of graphs

图的词典积的优惠券着色

A symmetric digraph is obtained from an undirected graph by replacing each edge uv of by a pair of opposite arcs and . An arc-colouring of a digraph is called distinguishing if the only automorphism preserving it is the identity. The least number of colours in a distinguishing arc-colouring, not necessarily proper, of is called the distinguishing index D'(). We study bounds for D'(). For proper distinguishing arc-colourings, the least number of colours is called the distinguishing chromatic index of . There are 15 possible types of proper arc-colourings of a digraph depending on the definition of adjacent arcs. In this paper we investigate distinguishing chromatic indices of for the nine remaining types not considered in our two previous papers. We formulate several conjectures.

Rafał Kalinowski

Monika Pilśniak

Magdalena Prorok

Distinguishing arc-colourings of symmetric digraphs

对称有向图的弧着色区分

The zero-divisor graph Π(R) of a commutative ring R is the graph whose vertices are the elements of R such that the vertices u and v are adjacent if and only if uv = 0. If the graphs G and H have the same chromatic polynomial, then we say that they are chromatically equivalent (or χ−equivalent), written as G ∼ H. Suppose a graph is uniquely determined by its chromatic polynomial. Then it is said to be chromatically unique (or χ-unique). In this paper, we discuss the question: For which numbers n is the graph Π(Zn) χ-unique? While Zn is one of the simplest rings, we proved that for any graph A0, for some n, Π(Zn) contains an induced subgraph isomorphic to A0. The first result in the subject states that for n ≥ 10 even, Π(Zn) is not χ-unique (Gehet, Khalaf). By definition, n is square-free if it is prime or the product of different prime numbers. Our main result is the following. If n ≥ 10 is neither square-free nor the square of a prime then it is not χ-unique. Here and in our preceding work, we use a common method. For odd square-free non-prime n, the problem is open, though on the structure of Π(Zn) we know much in this case.

Haneen Al-Janabi

Gábor Bacsó

Chromatic uniqueness of zero-divisor graphs

零除子图的色唯一性

David Callan

Ascent sequences avoiding a triple of 3-letter patterns and Fibonacci numbers

避免三字母模式和斐波那契数的上升序列

This paper is an update of a result published by Schulte and Wills in 1986. It explains in detail the construction of the polyhedral embedding of Coxeter's regular map of type {8, 4 ∣ 3} in Euclidean 3-space. The explanation is supported by numerous computer generated pictures. This polyhedron has the full octahedral symmetry group of order 48, and its combinatorial automorphism group is of order 482. It should be considered in context to additional five Leonardo polyhedra described recently by the authors in this journal.

Jürgen Bokowski

Jörg M. Wills

An E³ embedding of Coxeter’s regular map {8, 4 | 3} results in a regular Leonardo polyhedron

Coxeter的正则地图{8, 4 | 3}的E³嵌入产生一个正则莱昂纳多多面体

A vertex-transitive graph is a Cayley graph if and only if it admits a group of automorphisms acting regularly on its set of vertices. We generalize Cayley graphs to k-uniform hypergraphs, i.e. pairs (V, ℰ) where ℰ consists of k-subsets of V, k ≥ 2. We call a k-uniform hypergraph Cayley if and only if the hypergraph admits a group of automorphisms acting regularly on the vertex set of the hypergraph. We compare our definition with two other generalizations of Cayley graphs to hypergraphs found in the literature, and argue that ours is the most general; the other generalizations are special cases of the one proposed in this article. We present some basic properties of Cayley hypergraphs, discuss the connection of this concept to some recent results concerning hypergraphs, as well as connections to our ongoing project of constructing k-uniform hypergraphs whose full automorphism group is isomorphic to a prescribed finite group G and acts regularly on the vertices of the hypergraph.

Tatiana B. Jajcayová

Robert Jajcay

Generalizations of Cayley graphs to uniform hypergraphs

Cayley图到一致超图的推广

The restricted Hanoi graphs correspond to the variants of the Tower of Hanoi problem with restricted disc moves. In a such variant, moves of discs are restricted throughout the arcs of a movement digraph, whose vertices represent the pegs, and an arc from vertex p to vertex q exists if and only if moves from peg p to peg q are allowed. In this paper, we present two algorithms to generate the restricted Hanoi graphs based on the characterization of its arcs, giving also their time complexity. Then, we establish some combinatorial results on these graphs, such as the number of arcs, the number of vertices that allows a certain disc to be moved, as well as the degree of any arbitrary vertex.

El-Mehdi Mehiri

On the restricted Hanoi graphs

关于受限汉诺塔图

涉及主题	数学计算机科学组合数学离散数学理论计算机科学图形物理纯数学几何学数学分析量子力学哲学化学折线图工程类
出版信息	出版商: University of Primorska，出版周期: ，期刊类型: journal，开源期刊: 否
基本数据	创刊年份: 2018，原创研究文献占比: 0.00%，自引率:N.A.， Gold OA占比: 0.00%

Art of Discrete and Applied Mathematics

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享

On the maximal sum of the entries of a matrix power

Self-dual polyhedra of given degree sequence

Coupon coloring of lexicographic product of graphs

Distinguishing arc-colourings of symmetric digraphs

Chromatic uniqueness of zero-divisor graphs

On the maximal sum of the entries of a matrix power

Ascent sequences avoiding a triple of 3-letter patterns and Fibonacci numbers

An E³ embedding of Coxeter’s regular map {8, 4 | 3} results in a regular Leonardo polyhedron

Generalizations of Cayley graphs to uniform hypergraphs

On the restricted Hanoi graphs

ISSN	2590-9770
h-index	6