Search results for "Combinatorics"
showing 10 items of 1770 documents
Partially Square Graphs, Hamiltonicity and Circumference II
2000
Abstract Given a graph G, its partially square graph G∗ is a graph obtained by adding an edge uv for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition NG(x) ⊆ NG[u] ∪ NG[v], where NG[x]= NG(x) ∪ {x}. In case G is a claw-free graph, G∗ is equal to G2, We define σ ∗ t = min{ ∑ x∈ d ∗ G (x): S is an independent set in G ∗ and ∣S∣ = t} , where d ∗ G (x) = ∣{y ∈ V∣ xy ∈ E(G∗)}∣ . We give for hamiltonicity and circumference new sufficient conditions depending on and we improve some known results.
Common Fixed Points in a Partially Ordered Partial Metric Space
2013
In the first part of this paper, we prove some generalized versions of the result of Matthews in (Matthews, 1994) using different types of conditions in partially ordered partial metric spaces for dominated self-mappings or in partial metric spaces for self-mappings. In the second part, using our results, we deduce a characterization of partial metric 0-completeness in terms of fixed point theory. This result extends the Subrahmanyam characterization of metric completeness.
Divisible designs from semifield planes
2002
AbstractWe give a general method to construct divisible designs from semifield planes and we use this technique to construct some divisible designs. In particular, we give the case of twisted field plane as an example.
On the listing and random generation of hybrid binary trees
1994
We consider in this paper binary trees whose internal nodes are either associative or non-associative. Hybrid binary trees are equivalence classes with respect to the associative property. We count, list and generate randomly hybrid binary trees using Fibonacci numbers.
Root-restricted Kleenean rotations
2010
We generalize the Kleene theorem to the case where nonassociative products are used. For this purpose, we apply rotations restricted to the root of binary trees.
Generation of Valid Labeled Binary Trees
2003
International audience; Generating binary trees is a well-known problem. In this paper, we add some constraints to leaves of these trees. Such trees are used in the morphing of polygons, where a polygon P is represented by a binary tree T and each angle of P is a weight on a leaf of T. In the following, we give two algorithms to generate all binary trees, without repetitions, having the same weight distribution to their leaves and representing all parallel polygons to P.
Two graphs with a common edge
2014
Let G = G1 ∪ G2 be the sum of two simple graphs G1,G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant det A(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples
A bijection between words and multisets of necklaces
2012
Two of the present authors have given in 1993 a bijection Phi between words on a totally ordered alphabet and multisets of primitive necklaces. At the same time and independently, Burrows and Wheeler gave a data compression algorithm which turns out to be a particular case of the inverse of Phi. In the present article, we show that if one replaces in Phi the standard permutation of a word by the co-standard one (reading the word from right to left), then the inverse bijection is computed using the alternate lexicographic order (which is the order of real numbers given by continued fractions) on necklaces, instead of the lexicographic order as for Phi(-1). The image of the new bijection, ins…
Total and fractional total colourings of circulant graphs
2008
International audience; In this paper, the total chromatic number and the fractional total chromatic number of circulant graphs are studied. For cubic circulant graphs we give upper bounds on the fractional total chromatic number and for 4-regular circulant graphs we find the total chromatic number for some cases and we give the exact value of the fractional total chromatic number in most cases.
Fixed point theory for multivalued generalized nonexpansive mappings
2012
A very general class of multivalued generalized nonexpansive mappings is defined. We also give some fixed point results for these mappings, and finally we compare and separate this class from the other multivalued generalized nonexpansive mappings introduced in the recent literature.