Search

Your search keyword '"Miller, Mirka"' showing total 415 results
Start Over Author "Miller, Mirka"
415 results on '"Miller, Mirka"'

101. Preface

Author

Arumugam, S., primary, Froncek, Dalibor, additional, Ryan, Joe, additional, Ariyanti Sugeng, Kiki, additional, Baca, Martin, additional, and Miller, Mirka, additional

Published
2015
Full Text
View/download PDF

104. Preface

Author

Simanjuntak, Rinovia, primary, Baskoro, Edy Tri, additional, and Miller, Mirka, additional

Published
2015
Full Text
View/download PDF

106. On the nonexistence of almost Moore digraphs

Author

Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. TN - Grup de Recerca en Teoria de Nombres, Conde Colom, Josep, Gimbert Quintilla, Joan, González Rovira, Josep, Miller, Mirka, Miret Biosca, Josep Maria, Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. TN - Grup de Recerca en Teoria de Nombres, Conde Colom, Josep, Gimbert Quintilla, Joan, González Rovira, Josep, Miller, Mirka, and Miret Biosca, Josep Maria

Abstract

Digraphs of maximum out-degree at most d > 1, diameter at most k > 1 and order N(d, k) = d + ... + d(k) are called almost Moore or (d, k)-digraphs. So far, the problem of their existence has been solved only when d = 2, 3 or k = 2, 3, 4. In this paper we derive the nonexistence of (d, k)-digraphs, with k > 4 and d > 3, under the assumption of a conjecture related to the factorization of the polynomials Phi(n)(1 + x + ... + x(k)), where Phi(n)(x) denotes the nth cyclotomic polynomial and 1 < n <= N(d, k). Moreover, we prove that almost Moore digraphs do not exist for the particular cases when k = 5 and d = 4, 5 or 6. (C) 2014 Elsevier Ltd. All rights reserved., Postprint (published version)

Published
2014

107. Three Complexity Results on Coloring $P_k$-Free Graphs

Author

Broersma, Haitze J., Fomin, Fedor V., Golovach, Petr A., Paulusma, Daniël, Fiala, Jiri, Kratochvil, Jan, Miller, Mirka, and Discrete Mathematics and Mathematical Programming

Subjects
Discrete mathematics, Computational Complexity, EWI-17840, 0102 computer and information sciences, 02 engineering and technology, METIS-266491, Pk-free graph, IR-71249, 01 natural sciences, 1-planar graph, Graph coloring, Metric dimension, Combinatorics, Indifference graph, Pathwidth, 010201 computation theory & mathematics, Chordal graph, Partial k-tree, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Maximal independent set, Cograph, Mathematics
Abstract

We prove three complexity results on vertex coloring problems restricted to $P_k$-free graphs, i.e., graphs that do not contain a path on $k$ vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to $P_6$-ree graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on $P_5$-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for $P_6$-free graphs. This implies a simpler algorithm for checking the 3-colorability of $P_6$-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for $P_7$-free graphs. This problem was known to be polynomially solvable for $P_5$-free graphs and NP-complete for $P_8$-free graphs, so there remains one open case.

Published
2009

110. On the Partition Dimension of Circulant Graphs.

Author

GRIGORIOUS, CYRIAC, STEPHEN, SUDEEP, RAJAN, BHARATI, and MILLER, MIRKA

Subjects
GRAPH connectivity, PARTITIONS (Mathematics), VECTORS (Calculus), MATHEMATICAL connectedness, GRAPH theory
Abstract

For a vertex v of a connected graph G (V, E) and a subset S of V, the distance between v and S is defined by d(v,S) = mind{d(v,x): x ∈ S}. For an ordered k-partition π = {S1, SS2, ...,S2..., S k} of V, the representation of v with respect to π is the k-vector r(v|π} = (d(v,S1), d(v,S2, ..., d (v,Sk. The k-partition π is a resolving partition if the k-vectors r(v|π ), v V∈ V are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. In this paper, we obtain the partition dimension of circulant graphs G - C (n, ± {1,2,...,j}), 1 < j <[n/2], n ≥ (j+k) (j+1) and n = k (mod 2j) as, Pd (G) = j + 1{when j is even and ged (k,2j) = 1,/when j is odd and k = 2m, 1 ≤ m ≤ j. [ABSTRACT FROM AUTHOR]

Published
2017
Full Text
View/download PDF

112. ON H-ANTIMAGICNESS OF DISCONNECTED GRAPHS.

Author

BAČA, MARTIN, MILLER, MIRKA, RYAN, JOE, and SEMANIČOVÁ-FEŇOVČĬKOVÁ, ANDREA

Subjects
*GRAPH theory, *GRAPH labelings, *MAGIC labelings, *GRAPHIC methods, *MATHEMATICAL analysis
Abstract

A simple graph G = (V, E) admits an H-covering if every edge in E belongs to at least one subgraph, of G isomorphic to a given graph H. Then the graph G is (a, d)-H-antimagic if there exists a bijection, f : V ∪ E → {1, 2 |V| + |E|} such that, for all subgraphs H' of G isomorphic to H, the H' -weights, wtf(H') = Σν∈ V(H) f (v) + Σν∈ E(H') f (e), form an arithmetic progression with the initial term a and the common difference d. When f (V) = {1, 2,..., |V|}, then G is said to be super (a, d)-H-antimagic. In this paper, we study super (a, d)-H-antimagic labellings of a disjoint union of graphs for d = |E(H)| - |V(H)|. [ABSTRACT FROM AUTHOR]

Published
2016
Full Text
View/download PDF

116. Editorial

Author

Donovan, Diane, Iliopoulos, Costas, and Miller, Mirka

Abstract

Journal of Automata, Languages and Combinatorics, Volume 8, Number 4, 2003, 555-555

Published
2003
Full Text
View/download PDF

117. On large bipartite graphs of diameter 3

Author

Feria-Purón, Ramiro, Miller, Mirka, Pineda Villavicencio, Guillermo, Feria-Purón, Ramiro, Miller, Mirka, and Pineda Villavicencio, Guillermo

Published
2013

119. Construction for antimagic generalized web graphs

Author

Rylands, Leanne J., University of Western Sydney, Phanalasy, Oudone, Ryan, Joe, Miller, Mirka, Rylands, Leanne J., University of Western Sydney, Phanalasy, Oudone, Ryan, Joe, and Miller, Mirka

Abstract

An antimagic labeling of a graph with q edges is a bijection from the set of edges to the set of integers {1, 2, ..., q} such that all vertex weights are pairwise distinct, where the vertex weight is the sum of labels of all edges incident with the vertex. Let [n] = {1, 2, ..., n}. A completely separating system on [n] is a collection C of subsets of [n] in which, for each pair a ≠ b ∈ [n], there exist A,B ∈ C such that a ∈ A, b ∉ A and b ∈ B, a ∉ B. Recently, a relationship between completely separating systems and labeling of graphs has been shown to exist. Based on this relationship, antimagic labelings of various graphs have been constructed. In this paper, we extend our method to produce more general results for generalized web graphs.

Published
2011

120. On graphs of defect at most 2

Author

Feria-Purón, Ramiro, Miller, Mirka, Pineda Villavicencio, Guillermo, Feria-Purón, Ramiro, Miller, Mirka, and Pineda Villavicencio, Guillermo

Published
2011

124. Preface

Author

Kratochvíl, Jan, primary and Miller, Mirka, additional

Published
2013
Full Text
View/download PDF

126. A Lower Bound for Dilation of an Embedding.

Author

RAJAN, R. SUNDARA, MANUEL, PAUL, RAJASINGH, INDRA, PARTHIBAN, N., and MILLER, MIRKA

Subjects
PARALLEL computers, EMBEDDING theorems, COMPUTER algorithms, COMPUTER network architectures, MATHEMATICAL bounds
Abstract

Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. In this paper, we introduce a technique to obtain a lower bound for dilation of an embedding. Moreover, we give algorithms to compute exact dilation of embedding circulant network into a triangular grid, Tower of Hanoi graph and Sierpinski gasket graph, proving that the lower bound obtained is sharp. [ABSTRACT FROM AUTHOR]

Published
2015
Full Text
View/download PDF

145. Minimum Linear Arrangement of Incomplete Hypercubes.

Author

Miller, Mirka, Rajan, R. Sundara, Parthiban, N., and Rajasingh, Indra

Subjects
*MATHEMATICAL optimization, *COMBINATORICS, *MATHEMATICAL analysis, *HYPERCUBE networks (Computer networks), *COMPUTER networks
Abstract

The minimum linear arrangement problem is a combinatorial optimization problem whose goal is to find a linear layout of a network in such way that a certain objective cost function is optimized. In this paper, we compute the minimum linear arrangement of incomplete hypercubes using graph embeddings. [ABSTRACT FROM AUTHOR]

Published
2015
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results