The number of spanning trees in an (r,s)‐semiregular graph and its line graph

For a graph G, a “spanning tree” in G is a tree that has the same vertex set as G. The number of spanning trees in a graph (network) G, denoted by t(G), is an important invariant of the graph (network) with lots of decisive applications in many disciplines. In the article by Sato (Discrete Math. 2007, 307, 237), the number of spanning trees in an (r, s)‐semiregular graph and its line graph are obtained. In this article, we give short proofs for the formulas without using zeta functions. Furthermore, by applying the formula that enumerates the number of spanning trees in the line graph of an (r, s)‐semiregular graph, we give a new proof of Cayley's Theorem. © 2013 Wiley Periodicals, Inc.     

The Odyssey of Entropy: Cryptography

After being introduced by Shannon as a measure of disorder and unavailable information, the notion of entropy has found its applications in a broad range of scientific disciplines. In this paper, we present a systematic review on the applications of entropy and related information-theoretical concepts in the design, implementation and evaluation of cryptographic schemes, algorithms, devices and systems. Moreover, we study existing trends, and establish a roadmap for future research in these areas.     

Degree-equipartite graphs

A graph $G$ of order $2n$ is called degree-equipartite if for every $n$-element set $A?V\left(G\right)$, the degree sequences of the induced subgraphs $G\left[A\right]$ and $G[V\left(G\right)?A]$ are the same. In this paper, we characterize all degree-equipartite graphs. This answers Problem 1 in the paper by Grünbaum et al. [B. Grünbaum, T. Kaiser, D. Král, and M. Rosenfeld, Equipartite graphs, Israel J. Math. 168 (2008) 431–444].     

Unweighted linear congruences with distinct coordinates and the Varshamov–Tenengolts codes

In this paper, we first give explicit formulas for the number of solutions of unweighted linear congruences with distinct coordinates. Our main tools are properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions. Then, as an application, we derive an explicit formula for the number of codewords in the Varshamov–Tenengolts code \(VT_b(n)\) with Hamming weight k, that is, with exactly k 1’s. The Varshamov–Tenengolts codes are an important class of codes that are capable of correcting asymmetric errors on a Z-channel. As another application, we derive Ginzburg’s formula for the number of codewords in \(VT_b(n)\), that is, \(|VT_b(n)|\). We even go further and discuss connections to several other combinatorial problems, some of which have appeared in seemingly unrelated contexts. This provides a general framework and gives new insight into all these problems which might lead to further work.     

A new synthesis of lysophosphatidylcholines and related derivatives. Use of p-toluenesulfonate for hydroxyl group protection

A new stereoselective synthesis of lysophosphatidylcholines is reported. The synthesis is based upon (1) the use of 3-p-toluenesulfonyl-sn-glycerol to provide the stereocenter for construction of the optically active lysophospholipid molecule, (2) tetrahydropyranylation of the secondary alcohol function to achieve orthogonal protection of the sn-2- and sn-3-glycerol positions, and (3) elaboration of the phosphodiester headgroup using a 2-chloro-1,3,2-dioxaphospholane/trimethylamine sequence. In the course of developing the synthesis it has been discovered that methoxyacetate displacement of the sn-3-p-toluenesulfonate yields a reactive methoxyacetyl ester, which in turn can be selectively cleaved with methanol/tert-butylamine, while the ester group at the sn-1-position remains unaffected. The sequence has been shown to be suitable for preparation of spectroscopically labeled lysophosphatidylcholines. One of these compounds was readily converted to a double-labeled mixed-chain phosphatidylcholine applicable for real-time fluorescence resonance energy transfer (FRET) assay of lipolytic enzymes. In addition, the work led to new synthetic strategies based on chemoselective manipulation of the tosyl group in the presence of other base-labile groups such as FMOC derivatives that are often used for the protection of amino and hydroxyl groups in syntheses.     

A generalization of Schönemann’s theorem via a graph theoretic method

Recently, Grynkiewicz et al. (2013), using tools from additive combinatorics and group theory, proved necessary and sufficient conditions under which the linear congruence $a_1{x}_1+?+a_k{x}_k\equiv b(modn)$, where $a_1,\dots ,a_k,b,n$ ($n\ge 1$) are arbitrary integers, has a solution $〈x_1,\dots ,x_k〉\in {\mathbb{Z}}_n^k$ with all $x_i$ distinct. So, it would be an interesting problem to give an explicit formula for the number of such solutions. Quite surprisingly, this problem was first considered, in a special case, by Schönemann almost two centuries ago(!) but his result seems to have been forgotten. Schönemann (1839), proved an explicit formula for the number of such solutions when $b=0$, $n=p$ a prime, and ${\sum }_{i=1}^k{a}_i\equiv 0(modp)$ but ${\sum }_{i\in I}{a}_i?\equiv 0(modp)$ for all $0?\ne I??\{1,\dots ,k\}$. In this paper, we generalize Schönemann’s theorem using a result on the number of solutions of linear congruences due to D. N. Lehmer and also a result on graph enumeration. This seems to be a rather uncommon method in the area; besides, our proof technique or its modifications may be useful for dealing with other cases of this problem (or even the general case) or other relevant problems.     

A new approach to phospholipid synthesis using tetrahydropyranyl glycerol: rapid access to phosphatidic acid and phosphatidylcholine, including mixed-chain glycerophospholipid derivatives

A new synthesis of phosphatidic acid and phosphatidylcholine is reported, relying on the preparation of 3-tetrahydropyranyl-sn-glycerol as the key intermediate for sequential introduction of the primary and secondary acyl functions to produce chiral diglycerides that are phosphorylated to obtain the target phospholipid compounds.     

Cryptography in Hierarchical Coded Caching: System Model and Cost Analysis

The idea behind network caching is to reduce network traffic during peak hours via transmitting frequently-requested content items to end users during off-peak hours. However, due to limited cache sizes and unpredictable access patterns, this might not totally eliminate the need for data transmission during peak hours. Coded caching was introduced to further reduce the peak hour traffic. The idea of coded caching is based on sending coded content which can be decoded in different ways by different users. This allows the server to service multiple requests by transmitting a single content item. Research works regarding coded caching traditionally adopt a simple network topology consisting of a single server, a single hub, a shared link connecting the server to the hub, and private links which connect the users to the hub. Building on the results of Sengupta et al. (IEEE Trans. Inf. Forensics Secur., 2015), we propose and evaluate a yet more complex system model that takes into consideration both throughput and security via combining the mentioned ideas. It is demonstrated that the achievable rates in the proposed model are within a constant multiplicative and additive gap with the minimum secure rates.     

From Random Numbers to Random Objects

Many security-related scenarios including cryptography depend on the random generation of passwords, permutations, Latin squares, CAPTCHAs and other types of non-numerical entities. Random generation of each entity type is a different problem with different solutions. This study is an attempt at a unified solution for all of the mentioned problems. This paper is the first of its kind to pose, formulate, analyze and solve the problem of random object generation as the general problem of generating random non-numerical entities. We examine solving the problem via connecting it to the well-studied random number generation problem. To this end, we highlight the challenges and propose solutions for each of them. We explain our method using a case study; random Latin square generation.