Faculty Publications

Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736

Publications by NITK Faculty

Browse

Subject: search.filters.subject.Combinatorial mathematics

Search Results

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    On induced colourful paths in triangle-free graphs
    (Elsevier B.V., 2019) Babu, J.; Basavaraju, M.; Sunil Chandran, L.S.; Francis, M.C.
    Given a graph G=(V,E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai–Roy–Vitaver Theorem that every properly coloured graph contains a colourful path on ?(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on ?(G) vertices and prove its correctness when the girth of G is at least ?(G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if ?(G)?f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G. © 2018 Elsevier B.V.
  • No Thumbnail Available
    Item
    Shrinking generators based on ?-LFSRs
    (Elsevier B.V., 2020) Bishoi, S.K.; Senapati, K.; Shankar, B.R.
    The word-based LFSRs called ?-LFSRs are very attractive as they take advantage of the modern word-based processor and thus increase the throughput. Secondly, the bitstream produced by ?-LFSR has excellent statistical properties with a high period except for low linear complexity. In order to increase the linear complexity, the concept of both bit-oriented shrinking and self-shrinking generators is introduced in case of ?-LFSRs. In both the cases, the lower bound for the period as well as for the linear complexity of the bitstream are shown to be exponential. Further, we have experimented and investigated more results on the periodicity and statistical properties of the bitstream in self-shrinking ?-LFSRs. This helps to find and prove the exact period of the bitstream produced by self-shrinking generators. © 2020 Elsevier B.V.