Page 1 Next

Displaying 1 – 20 of 149

Showing per page

A characterization of complete tripartite degree-magic graphs

Ľudmila Bezegová, Jaroslav Ivančo (2012)

Discussiones Mathematicae Graph Theory

A graph is called degree-magic if it admits a labelling of the edges by integers 1, 2,..., |E(G)| such that the sum of the labels of the edges incident with any vertex v is equal to (1+ |E(G)|)/2*deg(v). Degree-magic graphs extend supermagic regular graphs. In this paper we characterize complete tripartite degree-magic graphs.

A magical approach to some labeling conjectures

Ramon M. Figueroa-Centeno, Rikio Ichishima, Francesc A. Muntaner-Batle, Akito Oshima (2011)

Discussiones Mathematicae Graph Theory

In this paper, a complete characterization of the (super) edge-magic linear forests with two components is provided. In the process of establishing this characterization, the super edge-magic, harmonious, sequential and felicitous properties of certain 2-regular graphs are investigated, and several results on super edge-magic and felicitous labelings of unions of cycles and paths are presented. These labelings resolve one conjecture on harmonious graphs as a corollary, and make headway towards the...

A note on on-line ranking number of graphs

Gabriel Semanišin, Roman Soták (2006)

Czechoslovak Mathematical Journal

A k -ranking of a graph G = ( V , E ) is a mapping ϕ V { 1 , 2 , , k } such that each path with endvertices of the same colour c contains an internal vertex with colour greater than c . The ranking number of a graph G is the smallest positive integer k admitting a k -ranking of G . In the on-line version of the problem, the vertices v 1 , v 2 , , v n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G [ { v 1 , v 2 , , v i } ] are known when the colour for the vertex v i has to be chosen. The on-line ranking number of a graph G is the smallest...

A note on radio antipodal colourings of paths

Riadh Khennoufa, Olivier Togni (2005)

Mathematica Bohemica

The radio antipodal number of a graph G is the smallest integer c such that there exists an assignment f V ( G ) { 1 , 2 , ... , c } satisfying | f ( u ) - f ( v ) | D - d ( u , v ) for every two distinct vertices u and v of G , where D is the diameter of G . In this note we determine the exact value of the antipodal number of the path, thus answering the conjecture given in [G. Chartrand, D. Erwin and P. Zhang, Math. Bohem. 127 (2002), 57–69]. We also show the connections between this colouring and radio labelings.

A note on strongly multiplicative graphs

Chandrashekar Adiga, H.N. Ramaswamy, D.D. Somashekara (2004)

Discussiones Mathematicae Graph Theory

In this note we give an upper bound for λ(n), the maximum number of edges in a strongly multiplicative graph of order n, which is sharper than the upper bound obtained by Beineke and Hegde [1].

A Note on the Total Detection Numbers of Cycles

Henry E. Escuadro, Futaba Fujie, Chad E. Musick (2015)

Discussiones Mathematicae Graph Theory

Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . . , k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . . , ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value val(c) of...

A polynomial algorithm for minDSC on a subclass of series Parallel graphs

Salim Achouri, Timothée Bossart, Alix Munier-Kordon (2009)

RAIRO - Operations Research

The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.

Altitude of wheels and wheel-like graphs

Tomasz Dzido, Hanna Furmańczyk (2010)

Open Mathematics

An edge-ordering of a graph G=(V, E) is a one-to-one mapping f:E(G)→{1, 2, ..., |E(G)|}. A path of length k in G is called a (k, f)-ascent if f increases along the successive edges forming the path. The altitude α(G) of G is the greatest integer k such that for all edge-orderings f, G has a (k, f)-ascent. In our paper we give exact values of α(G) for all helms and wheels. Furthermore, we use our result to obtain altitude for graphs that are subgraphs of helms.

An upper bound for maximum number of edges in a strongly multiplicative graph

Chandrashekar Adiga, Mahadev Smitha (2006)

Discussiones Mathematicae Graph Theory

In this note we give an upper bound for λ(n), the maximum number of edges in a strongly multiplicative graph of order n, which is sharper than the upper bounds given by Beineke and Hegde [3] and Adiga, Ramaswamy and Somashekara [2], for n ≥ 28.

Arithmetic labelings and geometric labelings of countable graphs

Gurusamy Rengasamy Vijayakumar (2010)

Discussiones Mathematicae Graph Theory

An injective map from the vertex set of a graph G-its order may not be finite-to the set of all natural numbers is called an arithmetic (a geometric) labeling of G if the map from the edge set which assigns to each edge the sum (product) of the numbers assigned to its ends by the former map, is injective and the range of the latter map forms an arithmetic (a geometric) progression. A graph is called arithmetic (geometric) if it admits an arithmetic (a geometric) labeling. In this article, we show...

Classes of hypergraphs with sum number one

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph d ̲ , d ̅ ( S ) = ( V , ) where V = S and = e S : d ̲ < | e | < d ̅ v e v S . For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices w , . . . , w σ V such that w , . . . , w σ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition for the edgecardinalities...

Cordial deficiency.

Riskin, Adrian (2007)

Bulletin of the Malaysian Mathematical Sciences Society. Second Series

Currently displaying 1 – 20 of 149

Page 1 Next