Vol. 16 no. 2

1. 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 […]
Section: PRIMA 2013

2. 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 […]
Section: PRIMA 2013

3. On additive combinatorics of permutations of ℤ<sub>n</sub>

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

4. 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 […]
Section: PRIMA 2013

5. 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 […]
Section: PRIMA 2013

6. 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 […]
Section: PRIMA 2013

7. 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 […]
Section: PRIMA 2013

8. 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 […]
Section: PRIMA 2013

9. 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 […]
Section: PRIMA 2013

10. 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 […]
Section: PRIMA 2013