BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
With the aid of hypergraph transversals it is proved that γt(Qn+1)=2γ(Qn), where γt(G) and γ(G) denote the total domination number and the domination number of G, respectively, and Qn is the n-dimensional hypercube. More generally, it is shown that if G is a bipartite graph, then γt(G□K2)=2γ(G). Further, we show that the bipartite condition is essential by constructing, for any k≥1, a (non-bipartite) graph G such that γt(G□K2)=2γ(G)−k. Along the way several domination-type identities for hypercubes are also obtained.
We show that there is no (95,40,12,20) strongly regular graph and, consequently, there is no (96,45,24,18) strongly regular graph, no two-graph on 96 vertices, and no partial geometry pg(5,9,3). The main idea of the result is based on the star complement technique and requires a small amount of computation.
The generalized Fibonacci cube Qd(f) is the subgraph of the d-cube Qd induced on the set of all strings of length d that do not contain f as a substring. It is proved that if Qd(f)≅Qd(f′) then ∣f∣=∣f′∣. The key tool to prove this result is a result of Guibas and Odlyzko about the autocorrelation polynomial associated to a binary string. It is also proved that there exist pairs of strings f,f′ such that Qd(f)≅Qd(f′), where ∣f∣≥32(d+1) and f′ cannot be obtained from f by its reversal or binary complementation. Strings f and f′ with ∣f∣=∣f′∣=d−1 for which Qd(f)≅Qd(f′) are characterized.
The Fibonacci cube Γn is obtained from the n-cube Qn by removing all the vertices that contain two consecutive 1s. If, in addition, the vertices that start and end with 1 are removed, the Lucas cube Λn is obtained. The number of vertex and edge orbits, the sets of the sizes of the orbits, and the number of orbits of each size, are determined for the Fibonacci cubes and the Lucas cubes under the action of the automorphism group. In particular, the set of the sizes of the vertex orbits of Λn is $\{k \ge 1;\ k \divides n\} \cup\, \{k \ge 18;\ k \divides 2n\}$, the number of the vertex orbits of Λn of size k, where k is odd and divides n, is equal to $\sum_{d\divides k}μ\left(\frac{k}{d}\right) F_{\lfloor \frac{d}{2}\rfloor + 2}$, and the number of the edge orbits of Λn is equal to the number of the vertex orbits of Γn−3. Dihedral transformations of strings and primitive strings are essential tools to prove these results.
Let D be the distance matrix of a connected graph G and let nn(G), np(G) be the number of strictly negative and positive eigenvalues of D respectively. It was remarked in [1] that it is not known whether there is a graph for which np(G) > nn (G). In this note we show that there exists an infinite number of graphs satisfying the stated inequality, namely the conference graphs of order> 9. A large representative of this class being the Paley graphs.The result is obtained by derving the eigenvalues of the distance matrix of a strongly-regular graph.
Let α(n) be the least number k for which there exists a simple graph with k vertices having precisely n≥3 spanning trees. Similarly, define β(n) as the least number k for which there exists a simple graph with k edges having precisely n≥3 spanning trees. As an n-cycle has exactly n spanning trees, it follows that α(n),β(n)≤n. In this paper, we show that α(n)≤3n+4 and β(n)≤3n+7 if and only if n∈/3,4,5,6,7,9,10,13,18,22, which is a subset of Euler's idoneal numbers. Moreover, if n≡2(mod3) and n=25 we show that α(n)≤4n+9 and β(n)≤4n+13. This improves some previously known bounds.
Can a non self-complementary graph have the same chromatic polynomial as its complement? The answer to this question of Akiyama and Harrary is positive and was given by J. Xu and Z. Liu. They conjectured that every such graph has the same degree sequence as its complement. In this paper we show that there are infinitely many graphs for which this conjecture does not hold. We then solve a more general variant of the Akiyama-Harary problem by showing that there exists infinitely many non self-complementary graphs having the same Tutte polynomial as their complements.
Let A_n (n >= 1) be the set of all integers x such that there exists a connected graph on n vertices with precisely x spanning trees. In this paper, we show that |A_n| grows faster than sqrt{n}exp(2Pi*sqrt{n/log{n}/Sqrt(3)} This settles a question of Sedlacek.
Let ρ(G) denote the number of convex cycles of a simple graph G of order n, size m, and girth 3 <= g <=n. It is proved that ρ(G)≤gn(m−n+1) and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.
Let G1 and G2 be simple graphs and let n1=∣V(G1)∣, m1=∣E(G1)∣, n2=∣V(G2)∣ and m2=∣E(G2)∣. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G1□G2 of G1 and G2. We show that: τ(G1□G2)≥n1n22(n1−1)(n2−1)(τ(G1)n1)2n2+1(τ(G2)n2)2n1+1 and τ(G1□G2)≤τ(G1)τ(G2)[n1−12m1+n2−12m2](n1−1)(n2−1). We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in Kn1□Kn2 which turns out to be n1n1−2n2n2−2(n1+n2)(n1−1)(n2−1).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.