Source author record

Behnaz Omoomi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR

Catalog footprint

Research overview

18works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

A characterization of some graphs with metric dimension two

A set W \subseteq V (G) is called a resolving set, if for each pair of distinct vertices u,v \in V (G) there exists t \in W such that d(u,t) \neq d(v,t), where d(x,y) is the distance between vertices x and y. The cardinality of a minimum resolving set for G is called the metric dimension of G and is denoted by dim_M(G). A k-tree is a chordal graph all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k. A k-path is a k-tree with maximum degree 2k, where for each integer j, k \leq j < 2k, there exists a unique pair of vertices, u and v, such that deg(u) = deg(v) = j. In this paper, we prove that if G is a k-path, then dim_M(G) = k. Moreover, we provide a characterization of all 2-trees with metric dimension two.

preprint2015arXiv

Sigma clique covering of graphs

The sigma clique cover number (resp. sigma clique partition number) of graph G, denoted by scc(G) (resp. scp(G)), is defined as the smallest integer k for which there exists a collection of cliques of G, covering (resp. partitioning) all edges of G such that the sum of sizes of the cliques is at most k. In this paper, among some results we provide some tight bounds for scc and scp.

preprint2014arXiv

Pairwise Balanced Designs and Sigma Clique Partitions

In this paper, we are interested in minimizing the sum of block sizes in a pairwise balanced design, where there are some constraints on the size of one block or the size of the largest block. For every positive integers n;m, where m ? n, let S(n;m) be the smallest integer s for which there exists a PBD on n points whose largest block has size m and the sum of its block sizes is equal to s. Also, let S0(n;m) be the smallest integers for which there exists a PBD on n points which has a block of size m and the sum of it block sizes is equal to s. We prove some lower bounds for S(n;m) and S0(n;m). Moreover, we apply these bounds to determine the asymptotic behaviour of the sigma clique partition number of the graph Kn-Km, Cocktail party graphs and complement of paths and cycles.

preprint2013arXiv

On the simultaneous edge coloring of graphs

preprint2013arXiv

Small oriented cycle double cover of graphs

A small oriented cycle double cover (SOCDC)} of a bridgeless graph $G$ on $n$ vertices is a collection of at most $n-1$ directed cycles of the symmetric orientation, $G_s$ , of $G$ such that each edge of $G_s$ lies in exactly one of the cycles. It is conjectured that every 2-connected graph except two complete graphs $K_4$ and $K_6$ has an $\rm SOCDC$ . In this paper, we study graphs with $\rm SOCDC$ and obtain some properties of the minimal counterexample to this conjecture.

preprint2013arXiv

Some lower bounds for the $L$ -intersection number of graphs

For a set of non-negative integers $L$ , the $L$ -intersection number of a graph is the smallest number $l$ for which there is an assignment on the vertices to subsets $A_v \subseteq \{1,\dots, l\}$ , such that every two vertices $u,v$ are adjacent if and only if $|A_u \cap A_v|\in L$ . The bipartite $L$ -intersection number is defined similarly when the conditions are considered only for the vertices in different parts. In this paper, some lower bounds for the (bipartite) $L$ -intersection number of a graph for various types $L$ in terms of the minimum rank of graph are obtained.

preprint2012arXiv

A generalization of line graphs via link scheduling in wireless networks

In single channel wireless networks, concurrent transmission at different links may interfere with each other. To improve system throughput, a scheduling algorithm is necessary to choose a subset of links at each time slot for data trasmission. Throughput optimal link scheduling discipline in such a wireless network is generally an NP-hard problem. In this paper, we develop a poylnomial time algorithm for link scheduling problem provided that network conflict graph is line multigraph. (i.e. line graph for which its root graph is multigraph). This result can be a guideline for network designers to plan the topology of a stationary wireless network such that the required conditions hold and then the throughput optimal algorithm can be run in a much less time.

preprint2012arXiv

Local Clique Covering of Graphs

A k-clique covering of a simple graph G, is an edge covering of G by its cliques such that each vertex is contained in at most k cliques. The smallest k for which G admits a k-clique covering is called local clique cover number of G and is denoted by $lcc(G)$ . Local clique cover number can be viewed as the local counterpart of the clique cover number which is equal to the minimum total number of cliques covering all edges. In this paper, several aspects of the problem are studied and its relationships to other well-known problems are discussed. Moreover, the local clique cover number of claw-free graphs and its subclasses are notably investigated. In particular, it is proved that local clique cover number of every claw-free graph is at most $cΔ/ \logΔ$ , where $Δ$ is the maximum degree of the graph and $c$ is a universal constant. It is also shown that the bound is tight, up to a constant factor. Furthermore, it is established that local clique number of the linear interval graphs is bounded by $\logΔ+ 1/2 \log \logΔ+ O(1)$ . Finally, as a by-product, a new Bollobas-type inequality is obtained for the intersecting pairs of set systems.

preprint2012arXiv

On the 1-2-3-conjecture

A k-edge-weighting of a graph G is a function w: E(G)->{1,2,...,k}. An edge-weighting naturally induces a vertex coloring c, where for every vertex v in V(G), c(v) is sum of weights of the edges that are adjacent to vertex v. If the induced coloring c is a proper vertex coloring, then w is called a vertex-coloring k-edge weighting (VCk-EW). Karonski et al. (J. Combin. Theory Ser. B 91 (2004) 151-157) conjectured that every graph admits a VC3-EW. This conjecture is known as 1-2-3-conjecture. In this paper, frst, we study the vertex-coloring edge-weighting of the cartesian product of graphs. Among some results, we prove that the 1-2-3-conjecture holds for some infinite classes of graphs. Moreover, we explore some properties of a graph to admit a VC2-EW

preprint2012arXiv

On the Locating Chromatic Number of the Cartesian Product of Graphs

Let $c$ be a proper $k$ -coloring of a connected graph $G$ and $Π=(C_1,C_2,...,C_k)$ be an ordered partition of $V(G)$ into the resulting color classes. For a vertex $v$ of $G$ , the color code of $v$ with respect to $Π$ is defined to be the ordered $k$ -tuple $c_{{}_Π}(v):=(d(v,C_1),d(v,C_2),...,d(v,C_k)),$ where $d(v,C_i)=\min\{d(v,x) | x\in C_i\}, 1\leq i\leq k$ . If distinct vertices have distinct color codes, then $c$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$ , denoted by $\Cchi_{{}_L}(G)$. In this paper, we study the locating chromatic number of grids, the cartesian product of paths and complete graphs, and the cartesian product of two complete graphs.

preprint2012arXiv

On the oriented perfect path double cover conjecture

An {\sf oriented perfect path double cover} ( $\rm OPPDC$ ) of a graph $G$ is a collection of directed paths in the symmetric orientation $G_s$ of $G$ such that each edge of $G_s$ lies in exactly one of the paths and each vertex of $G$ appears just once as a beginning and just once as an end of a path. Maxov{á} and Ne{š}et{ř}il (Discrete Math. 276 (2004) 287-294) conjectured that every graph except two complete graphs $K_3$ and $K_5$ has an $\rm OPPDC$ and they proved that the minimum degree of the minimal counterexample to this conjecture is at least four. In this paper, among some other results, we prove that the minimal counterexample to this conjecture is 2-connected and 3-edge-connected.

preprint2012arXiv

Uniquely dimensional graphs

A set $W\subseteq V(G)$ is called a resolving set, if for each two distinct vertices $u,v\in V(G)$ there exists $w\in W$ such that $d(u,w)\neq d(v,w)$ , where $d(x,y)$ is the distance between the vertices $x$ and $y$ . A resolving set for $G$ with minimum cardinality is called a metric basis. A graph with a unique metric basis is called a uniquely dimensional graph. In this paper, we study some properties of uniquely dimensional graphs.

preprint2011arXiv

Characterization of n-Vertex Graphs with Metric Dimension n-3

For an ordered set $W=\{w_1,w_2,...,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$ , the ordered $k$ -vector $r(v|W):=(d(v,w_1),d(v,w_2),...,d(v,w_k))$ is called the (metric) representation of $v$ with respect to $W$ , where $d(x,y)$ is the distance between the vertices $x$ and $y$ . The set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$ . The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we characterize all graphs of order $n$ with metric dimension $n-3$ .

preprint2011arXiv

Characterization of Randomly k-Dimensional Graphs

For an ordered set $W=\{w_1,w_2,...,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$ , the ordered $k$ -vector $r(v|W):=(d(v,w_1),d(v,w_2),.,d(v,w_k))$ is called the (metric) representation of $v$ with respect to $W$ , where $d(x,y)$ is the distance between the vertices $x$ and $y$ . The set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$ . A minimum resolving set for $G$ is a basis of $G$ and its cardinality is the metric dimension of $G$ . The resolving number of a connected graph $G$ is the minimum $k$ , such that every $k$ -set of vertices of $G$ is a resolving set. A connected graph $G$ is called randomly $k$ -dimensional if each $k$ -set of vertices of $G$ is a basis. In this paper, along with some properties of randomly $k$ -dimensional graphs, we prove that a connected graph $G$ with at least two vertices is randomly $k$ -dimensional if and only if $G$ is complete graph $K_{k+1}$ or an odd cycle.

preprint2011arXiv

On Randomly k-Dimensional Graphs

For an ordered set $W=\{w_1,w_2,...,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$ , the ordered $k$ -vector $r(v|W):=(d(v,w_1),d(v,w_2),...,d(v,w_k))$ is called the (metric) representation of $v$ with respect to $W$ , where $d(x,y)$ is the distance between the vertices $x$ and $y$ . The set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$ . A resolving set for $G$ with minimum cardinality is called a basis of $G$ and its cardinality is the metric dimension of $G$ . A connected graph $G$ is called randomly $k$ -dimensional graph if each $k$ -set of vertices of $G$ is a basis of $G$ . In this paper, we study randomly $k$ -dimensional graphs and provide some properties of these graphs.

preprint2011arXiv

On the locating chromatic number of Kneser graphs

Let $c$ be a proper $k$ -coloring of a connected graph $G$ and $Π=(C_1,C_2,...,C_k)$ be an ordered partition of $V(G)$ into the resulting color classes. For a vertex $v$ of $G$ , the color code of $v$ with respect to $Π$ is defined to be the ordered $k$ -tuple $c_{{}_Π}(v):=(d(v,C_1),d(v,C_2),...,d(v,C_k)),$ where $d(v,C_i)=\min\{d(v,x) |x\in C_i\}, 1\leq i\leq k$ . If distinct vertices have distinct color codes, then $c$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$ , denoted by $\Cchi_{{}_L}(G)$. In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results we show that $\Cchi_{{}_L}(KG(n,2))=n-1$ for all $n\geq 5$ . Then, we prove that $\Cchi_{{}_L}(KG(n,k))\leq n-1$, when $n\geq k^2$ . Moreover, we present some bounds for the locating chromatic number of odd graphs.

preprint2011arXiv

Relations between Metric Dimension and Domination Number of Graphs

A set $W\subseteq V(G)$ is called a resolving set, if for each two distinct vertices $u,v\in V(G)$ there exists $w\in W$ such that $d(u,w)\neq d(v,w)$ , where $d(x,y)$ is the distance between the vertices $x$ and $y$ . The minimum cardinality of a resolving set for $G$ is called the metric dimension of $G$ , and denoted by $β(G)$ . In this paper, we prove that in a connected graph $G$ of order $n$ , $β(G)\leq n-γ(G)$ , where $γ(G)$ is the domination number of $G$ , and the equality holds if and only if $G$ is a complete graph or a complete bipartite graph $K_{s,t}$ , $s,t\geq 2$ . Then, we obtain new bounds for $β(G)$ in terms of minimum and maximum degree of $G$ .

preprint2011arXiv

The Metric Dimension of Lexicographic Product of Graphs

For an ordered set $W=\{w_1,w_2,...,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$ , the ordered $k$ -vector $r(v|W):=(d(v,w_1),d(v,w_2),...,d(v,w_k))$ is called the (metric) representation of $v$ with respect to $W$ , where $d(x,y)$ is the distance between the vertices $x$ and $y$ . The set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$ . The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we study the metric dimension of the lexicographic product of graphs $G$ and $H$ , $G[H]$ . First, we introduce a new parameter which is called adjacency metric dimension of a graph. Then, we obtain the metric dimension of $G[H]$ in terms of the order of $G$ and the adjacency metric dimension of $H$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Behnaz Omoomi

Research overview

Is this your work?

18 publications

A characterization of some graphs with metric dimension two

Sigma clique covering of graphs

Pairwise Balanced Designs and Sigma Clique Partitions

On the simultaneous edge coloring of graphs

Small oriented cycle double cover of graphs

Some lower bounds for the $L$ -intersection number of graphs

A generalization of line graphs via link scheduling in wireless networks

Local Clique Covering of Graphs

On the 1-2-3-conjecture

On the Locating Chromatic Number of the Cartesian Product of Graphs

On the oriented perfect path double cover conjecture

Uniquely dimensional graphs

Characterization of n-Vertex Graphs with Metric Dimension n-3

Characterization of Randomly k-Dimensional Graphs

On Randomly k-Dimensional Graphs

On the locating chromatic number of Kneser graphs

Relations between Metric Dimension and Domination Number of Graphs

The Metric Dimension of Lexicographic Product of Graphs

See the researcher in context

Building this map preview

Behnaz Omoomi

Research overview

Is this your work?

18 publications

A characterization of some graphs with metric dimension two

Sigma clique covering of graphs

Pairwise Balanced Designs and Sigma Clique Partitions

On the simultaneous edge coloring of graphs

Small oriented cycle double cover of graphs

Some lower bounds for the LLL-intersection number of graphs

A generalization of line graphs via link scheduling in wireless networks

Local Clique Covering of Graphs

On the 1-2-3-conjecture

On the Locating Chromatic Number of the Cartesian Product of Graphs

On the oriented perfect path double cover conjecture

Uniquely dimensional graphs

Characterization of n-Vertex Graphs with Metric Dimension n-3

Characterization of Randomly k-Dimensional Graphs

On Randomly k-Dimensional Graphs

On the locating chromatic number of Kneser graphs

Relations between Metric Dimension and Domination Number of Graphs

The Metric Dimension of Lexicographic Product of Graphs

See the researcher in context

Building this map preview

Some lower bounds for the $L$ -intersection number of graphs