PRIMA 2013

This section handles papers related to work that was presented at the special session on Combinatorics and Discrete Mathematics of the Second Pacific Rim Mathematical Association (PRIMA) Congress, held in Shanghai, China, June 24-28, 2013.</br>

Editors: Andreas Dress, Jing Huang, and Yaokun W.

Arithmetic completely regular codes

Koolen, Jacobus ; Sun Lee, Woo ; Martin, William ; Tanaka, Hajime.
In this paper, we explore completely regular codes in the Hamming graphs and related graphs. Experimental evidence suggests that many completely regular codes have the property that the eigenvalues of the code are in arithmetic progression. In order to better understand these "arithmetic completely […]

Spanning connectedness and Hamiltonian thickness of graphs and interval graphs

Li, Peng ; Wu, Yaokun.
A spanning connectedness property is one which involves the robust existence of a spanning subgraph which is of some special form, say a Hamiltonian cycle in which a sequence of vertices appear in an arbitrarily given ordering, or a Hamiltonian path in the subgraph obtained by deleting any three […]

Hamiltonian decomposition of prisms over cubic graphs

Rosenfeld, Moshe ; Xiang, Ziqing.
The prisms over cubic graphs are 4-regular graphs. The prisms over 3-connected cubic graphs are Hamiltonian. In 1986 Brian Alspach and Moshe Rosenfeld conjectured that these prisms are Hamiltonian decomposable. In this paper we present a short survey of the status of this conjecture, various […]

Nonrepetitive colorings of lexicographic product of graphs

Keszegh, Balázs ; Patkós, Balázs ; Zhu, Xuding.
A coloring c of the vertices of a graph G is nonrepetitive if there exists no path v1v2\textellipsisv2l for which c(vi)=c(vl+i) for all 1<=i<=l. Given graphs G and H with |V(H)|=k, the lexicographic product G[H] is the graph obtained by substituting every vertex of G by a copy of H, and every edge […]

The graph isomorphism problem on geometric graphs

Uehara, Ryuhei.
The graph isomorphism (GI) problem asks whether two given graphs are isomorphic or not. The GI problem is quite basic and simple, however, it\textquoterights time complexity is a long standing open problem. The GI problem is clearly in NP, no polynomial time algorithm is known, and the GI problem is […]

Complexity aspects of the computation of the rank of a graph

Ramos, Igor,  ; Santos, Vinícius F.,  ; Szwarcfiter, Jayme L..
We consider the P₃-convexity on simple undirected graphs, in which a set of vertices S is convex if no vertex outside S has two or more neighbors in S. The convex hull H(S) of a set S is the smallest convex set containing S as a subset. A set S is a convexly independent set if v \not ∈ H(S\setminus […]

Influence of the tie-break rule on the end-vertex problem

Charbit, Pierre ; Habib, Michel ; Mamcarz, Antoine.
End-vertices of a given graph search may have some nice properties, as for example it is well known that the last vertex of Lexicographic Breadth First Search (LBFS) in a chordal graph is simplicial, see Rose, Tarjan and Lueker 1976. Therefore it is interesting to consider if these vertices can be […]

A matroid associated with a phylogenetic tree

Dress, Andreas ; Huber, Katharina ; Steel, Mike.
A (pseudo-)metric D on a finite set X is said to be a \textquotelefttree metric\textquoteright if there is a finite tree with leaf set X and non-negative edge weights so that, for all x,y ∈X, D(x,y) is the path distance in the tree between x and y. It is well known that not every metric is a tree […]

On additive combinatorics of permutations of ℤn

Chandran, L. Sunil ; Rajendraprasad, Deepak ; Singh, Nitin.
Let ℤn denote the ring of integers modulo n. A permutation of ℤn is a sequence of n distinct elements of ℤn. Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of ℤn, […]

Uniquely monopolar-partitionable block graphs

Chen, Xuegang ; Huang, Jing.
As a common generalization of bipartite and split graphs, monopolar graphs are defined in terms of the existence of certain vertex partitions. It has been shown that to determine whether a graph has such a partition is NP-complete for general graphs and polynomial for several classes of graphs. In […]

Diversities and the Geometry of Hypergraphs

Bryant, David ; Tupper, Paul, .
The embedding of finite metrics in 1 has become a fundamental tool for both combinatorial optimization and large-scale data analysis. One important application is to network flow problems as there is close relation between max-flow min-cut theorems and the minimal distortion embeddings of metrics […]