Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 6
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however, the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Discrete Math. 331 (2014) 9–14].
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Metric dimension of maximal outerplanar graphs

  • Claverol Aguas, Mercè|||0000-0002-9138-8594
  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Maureso Sánchez, Montserrat|||0000-0001-6429-2776
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Hernández Peñalver, Gregorio
  • Garcia Olaverri, Alfredo Martin
  • Tejel, Javier
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Neighbor-locating colorings in graphs

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Pelayo Melero, Ignacio Manuel|||0000-0002-6523-0611
  • Alcón, Liliana
  • Gutierrez, Marisa
A k -coloring of a graph G is a k -partition ¿ = { S 1 ,...,S k } of V ( G ) into independent sets, called colors . A k -coloring is called neighbor-locating if for every pair of vertices u,v belonging to the same color S i , the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v . The neighbor-locating chromatic number ¿ NL ( G ) is the minimum cardinality of a neighbor-locating coloring of G . We establish some tight bounds for the neighbor-locating chromatic number of a graph, in terms of its order, maximum degree and independence number. We determine all connected graphs of order n = 5 with neighbor-locating chromatic number n or n - 1. We examine the neighbor-locating chromatic number for two graph operations: join and disjoint union, and also for two graph families: split graphs and Mycielski graphs
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

On quotient digraphs and voltage digraphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Miller, Mirka
  • Ryan, Joe
In this note we present a general approach to construct large digraphs from small ones. These are called expanded digraphs, and, as particular cases, we show their close relationship between voltage digraphs and line digraphs, which are two known approaches to obtain dense digraphs. In the same context, we show the equivalence between the vertex-splitting and partial line digraph techniques. Then, we give a sufficient condition for a lifted digraph of a base line digraph to be again a line digraph. Some of the results are illustrated with two well-known families of digraphs. Namely, De Bruijn and Kautz digraphs.
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Dominating 2- broadcast in graphs: complexity, bounds and extremal graphs

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Pelayo Melero, Ignacio Manuel|||0000-0002-6523-0611
  • Cáceres, José
  • Puertas, M. Luz
Limited dominating broadcasts were proposed as a variant of dominating broadcasts, where the broadcast function is upper bounded. As a natural extension of domination, we consider dominating 2-broadcasts along with the associated parameter, the dominating 2-broadcast number. We prove that computing the dominating 2-broadcast number is a NP-complete problem, but can be achieved in linear time for trees. We also give an upper bound for this parameter, that is tight for graphs as large as desired
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Graphs, Friends and Acquaintances

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
As is well known, a graph is a mathematical object modeling the existence of a certain relation between pairs of elements of a given set. Therefore, it is not surprising that many of the first results concerning graphs made reference to relationships between people or groups of people. In this article, we comment on four results of this kind, which are related to various general theories on graphs and their applications: the Handshake lemma (related to graph colorings and Boolean algebra), a lemma on known and unknown people at a cocktail party (to Ramsey theory), a theorem on friends in common (to distanceregularity and coding theory), and Hall’s Marriage theorem (to the theory of networks). These four areas of graph theory, often with problems which are easy to state but difficult to solve, are extensively developed and currently give rise to much research work. As examples of representative problems and results of these areas, which are discussed in this paper, we may cite the following: the Four Colors Theorem (4CTC), the Ramsey numbers, problems of the existence of distance-regular graphs and completely regular codes, and finally the study of topological proprieties of interconnection networks.