More results on greedy defining sets

zbMATH Open1340.05088arXiv0811.0454MaRDI QIDQ5248305

Author name not available (Why is that?)

Publication date: 6 May 2015

Abstract: The greedy defining sets of graphs were appeared first time in [M. Zaker, Greedy defining sets of graphs, Australas. J. Combin, 2001]. We show that to determine the greedy defining number of bipartite graphs is an NP-complete problem. This result answers affirmatively the problem mentioned in the previous paper. It is also shown that this number for forests can be determined in polynomial time. Then we present a method for obtaining greedy defining sets in Latin squares and using this method, show that any

n i m e s n

Latin square has a GDS of size at most

n^{2} - (n l o g n) / 4

. Finally we present an application of greedy defining sets in designing practical secret sharing schemes.

Full work available at URL: https://arxiv.org/abs/0811.0454

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: More results on greedy defining sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248305)